ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGÔ THỊ BÍCH NGỌC
MỘT SỐ KỸ THUẬT GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC
TIÊU THEO HƯỚNG QUY VỀ MỘT MỤC TIÊU
LUẬN VĂN THẠC SỸ TOÁN HỌC
THÁI NGUYÊN - NĂM 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGÔ THỊ BÍCH NGỌC
MỘT SỐ KỸ THUẬT GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC
TIÊU THEO HƯỚNG QUY VỀ MỘT MỤC TIÊU
LUẬN VĂN THẠC SỸ TOÁN HỌC
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.36
Người hướng dẫn khoa học:
TS. VŨ MẠNH XUÂN
THÁI NGUYÊN - NĂM 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 1 -

MC LC
Trang
Mc lc 1
Danh mc bng 3
Danh mc hình 3
Danh mc các ch vit tt 4
M U …5
Chng 1: TNG QUAN V TI U A MC TIÊU 7
1.1. Mt s bài toán c th 7

2.4.3. Bài toán 3 52
2.4.4. Bài toán 4 54
K(T LU)N 57
TÀI LI*U THAM KHO 58

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 3 -

DANH MC BNG BIU +ng 1.1. Chi phí xây d"ng 11
+ng 1.2. Bng thng ph,t 15
Bng 2.1.  thích nghi trung bình sau 5 ln ch,y c lp 46
Bng 2.2. Mt s l$i gii ca bài toán 1 theo phng pháp tr'ng s 48
Bng 2.3.

Giá tr trung nh ca 3 hàm mc tiêu sau 4 ln ch,y c lp 50
Bng 2.4. /0123425a 51c 67m 8c tiêu 592236:ch nghi tt nh#t 50
Bng 2.5. Mt s l$i gii ca bài toán 2 theo phng pháp tr'ng s 51
+ng 2.6. Mt s l$i ca bài toán 3 53
+ng 2.7. Giá tr trung nh ca 3 hàm mc tiêu sau 5 ln ch,y c lp 55
+ng 2.8. /0123425a 51c 67m 8c tiêu 592236:ch nghi tt nh#t 55


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 5 -

M U
Nhi!u bài toán trong th"c t là nhng bài toán ti u, trong ó, ti u a mc
tiêu là l<p bài toán r#t th$ng g&p trong thit k, ch t,o c?ng nh nhi!u l@nh v"c
khác. ChAng h,n, khi ng$i ta ch t,o thit b thì luôn mong mun tn ít vt liu,
gim th$i gian c?ng nh vn u t trong khi ch#t lng phi tt. Tuy có ý ngh@a
th"c ti>n cao và c?ng ã c nghiên c;u nhi!u, song bài toán ti u a mc tiêu
luôn là mt thách th;c l<n vì chúng gn nh không có nghim ti u. Có nhng
mc tiêu c biu di>n bi nhng hàm tng t" nhau nhng yêu cu ti u theo
hai h<ng ngc nhau, ó là cha k n nhng khó khBn v! mi!n ràng buc, v!
các d,ng hàm s phi tuyn, thm chí không liên tc, …
V<i mong mun tìm hiu sâu v! l<p bài toán ti u a mc tiêu, tôi ã ch'n
! tài “Mt s kC thut gii bài toán ti u a mc tiêu theo h<ng quy v! mt

gi  tác gi có th hoàn thành bn lun vBn này.

Do h,n ch v! th$i gian, i!u kin nghiên c;u và s;c khe bn thân nên m&c
dù ã r#t c gng, song lun vBn m<i chF ,t c v! c bn mc tiêu &t ra.
Tác gi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 7 -

CHNG 1

TNG QUAN V TI U A MC TIÊU

Nhi!u bài toán ;ng dng trong các l@nh v"c khác nhau ca khoa h'c kC
thut c?ng nh th"c ti>n cuc sng ca con ng$i có th mô hình hoá bi mt
bài toán ti u. Th"c t, cùng mt lúc ng$i ta th$ng mun theo ui nhi!u
mc tiêu khác nhau (ví d: Khi l"a ch'n mua xe hay mua nhà , ng$i ta luôn
tính n nhi!u yu t nh giá c, hình th;c, tin nghi…, nhng th$ng giá rH
thì tin nghi ho&c hình th;c l,i kém hn…). i!u ó dDn n l<p bài toán ti
u a mc tiêu (quy ho,ch a mc tiêu). Chng 1 trình bày v! l<p bài toán
này qua mt s ví d c th, ng th$i nêu ra mt s phng pháp gii bài
toán ti u a mc tiêu.

f . x
2
2 2
= 05∗

Dung tích
f
3
ca h là :

. x
.
f e x x
1
0 0005∗
0 01 2
3 1 2
= ∗ ∗

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 8 -

Nh vy, ta có th phát biu bài toán:

( )
min( f )
min f
max( f )
1
2

, 
2
, …, 
N
, ng th$i thi n<c  h, lu (hình 1.1). H ch;a có tác
dng c#p n<c và thông r%a dòng chy  h, lu. Cn kim soát nhu cu ôxy
hóa B.O.D (Biochemical Oxygen Demand) ca mIi i tng s% dng n<c
bJng nng  ôxy tan trong n<c D.O và xác nh gi<i h,n lng n<c thi
phi x% lý ca mIi i tng c?ng nh lng n<c thông r%a tháo t= h ch;a
ra.
Gi s% các bin quyt nh
i
x (i , , N )
=1
là lng ch#t thi phi x% lý, cn
tha mãn i!u kin
i
. x .
0 45 ≤ ≤ 099
. G'i y là lng n<c cn thông r%a mà h
ch;a sE cung c#p cho h thng. Khi ó các mc tiêu cn ,t c là:
1) C"c tiu hóa giá thành x% lý n<c thi
2) C"c ,i hóa lng n<c tr trong h ch;a.
3) C"c tiu hóa nng  nhi>m bKn  dòng chy.
Tng giá thành x% lý n<c thi
f
1
c tính theo công th;c:
( ) ( )
N

Hình 1.1. S  h ch;a và dòng chy
Lng n<c tr trong h ch;a tính bi

f S y
2
= −
trong ó S là dung tích h ch;a.
Nng  ôxy trong n<c  dòng chy t,i b#t kL th$i im nào có th tính t=
phng trình Streeter-Phelps theo công th;c:

( )
( )
( )
N N
i i i
i i
a x . . a b y b c
f
c b b y
1 1 1
=1 =1
3
2 2 2
∗ −0 45 + 0 45 ∗ + ∗ + −
=
− − ∗
 

H ch;a


3






Trong ó, các hàm mc tiêu
f , f , f
1 2 3
xác nh nh trên, ng th$i các bin
i
x
và
y
cn tha mãn các i!u kin:

i
. x . , (i , ,N )
0 45 ≤ ≤0 99 =1
và
y S . .
0 ≤ ≤ =3 47

1.1.3. Bài toán thit k nhà 
Xét vic thit k nhà nh trong hình 1.2, cách b trí các phòng c?ng nh
mt s thông s và ràng buc c cho tr<c. V#n ! là cn xác nh các thông
s còn l,i sao cho tng din tích là l<n nh#t nhng tng chi phí l,i là nh nh#t.



3.98
x
3
3.05
3.35
3.98
x
1
x
2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 11 -
Chi phí xây d"ng c cho trong bng 1.1
Bng 1.1. Chi phí xây d"ng
   



  



!"  

 #  $$
 $ % $$
 # $ $$
 &% '& (&'
)*  (&# +&# (&'


2
là tng chi phí xây d"ng thì
F
2
là hàm s ca
x
1
, x
2
, x
3
, x
4
, x
5

theo
công th;c
F
2
=(4,28x
1
).300+ (2,45x
2
)324,7+ (1,83x
2
)324,7+ (3,05x
4
)200+ (3,05x
5

≤

- Phòng tm :


≤
≤

- Snh :


≤

- Phòng ng 1:


≤
≤

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 12 -
- Phòng ng 2:


≤
≤

- Phòng ng 3:





v<i các ràng buc (
R).

1.2. Bài toán tng quát
Ta có th phát biu bài toán ti u a mc tiêu d,ng tng quát nh sau

(
)
{
}
x D
min( max ) F x
∈
( 1.1)
v<i các ràng buc
0 1
n
i
g ( x ) , x , i , ,m
≥ ∈ =


Trong

ó:
n
D
⊆

là các hàm m

c tiêu.

Các bài toán t

i

u

a m

c tiêu th
$
ng có nhi
!
u hàm m

c tiêu v
<
i các ràng
bu

c khác nhau và các l
$
i gi

i khác nhau. Các l
$
i gi

vect y (kí hiu
x y

), n
u ta có:
F( x ) F( y )
≤
và
F( x ) F( y )
≠
, t

c là
{
}
(
)
(
)
i i
i , ,k : f x f y
∀ ∈ 1 ≤
và
{
}
(
)
(
)
j j



n
x
∈



c g

i là
nghim ti u Pareto
(hay
im Pareto
)
n

u không có
n
y∈

mà y tr

i h

n x.
T

p t


yu
n

u không t

n t

i
n
y∈


mà
F( y ) F( x )
<
.
N

u bài toán t

i

u

a m

c tiêu có nghi

m


i

u

ó ph

i là m

t nghi

m Pareto t

i

u (t
;
c là, nghi

m

ó ph

i thu

c t

p Pareto
t

i

,
t
min
.



ây các

i

m A, B, C là minh h
'
a cho hàm m

c vect

m

c
tiêu t
,
i các ph

ng án có th

có c

a bài toán. Ta nh


,
i l
<
n,

i

m B
có t
F
l

r

i ro th
#
p thì giá l
,
i cao. Các

i

m nh

v

y minh h
'
a cho hàm vect


a trên thì

i

m B là t

t h

n

i

m C.
A

B

C

f
1

(giá)
f
2

(ri ro)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 14 -
Trên th

n

c. Vì v

y, m

t s

chi

n l

c tìm ki

m ng
D
u
nhiên (nh

thu

t toán ti

n hóa, ph

ng pháp vùng c
#
m, mô ph

ng luy


ng
!
u c

g

ng tìm ra m

t t

p x
#
p x
F

t

t, t
;
c là m

t t

p các ph

ng án mà vect

m


(
)
k
k
, ,
ε ε ε
1 +
= ∈


(a)
V

i
n
x,y
∈

. x

c g

i là
ε
−
tri
h

n y (kí hi



i ít nh

t m

t
{
}
j , ,k
∈ 1
.
(b)
M

t t

p
n
F
ε
⊂


c g

i là m

t t

p

t
y F
ε
∈
, t

c là:

n
x , y F : y x
ε ε
∀ ∈ ∃ ∈


.
(c)
M

t t

p
* n
F
ε
⊂


c g

i là m

c
*
F
ε

u là

i

m Pareto.
1.3. Mt s phng pháp gii c th [2]
1.3.1. Phng pháp nh ng b d!n
Xét bài toán :

(
)
{
}
x D
max F x
∈

v
<
i các ràng bu

c 0 1
i
g ( x ) , x D ,i , ,m
≥ ∈ =

m
x*
mà theo ý thích c

a ng
$
i nh

n l
$
i gi

i thì
∀
x
⊂
D:
x* >x
ho
&
c
x*= x.

Thu

t toán :
Bc 0
: Gi

i

u .
0
i
f
là giá tr

t

i

u).
B

ng 1.2. B

ng th

ng ph
,
t.
Hàm m

c tiêu
Ph

ng án
f
1f
0
2… …
k
xk
f
0Bc 1
: C
B
n c
;
vào b

ng th

ng ph
,
t và
f

và gi

i bài toán:

(
)
x D
max f x
2
∈(
)
f x f f
0
1 1 1
≥ − ∆

Gi

s
%

f
∗
2
là giá tr

t

∗
2
, b

t f
2
nh

ng b

1 l

ng

∆
f
2
và gi

i bài toán:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 16 -
(
)
x D
max f x
3
∈

(

n sang b
<
c ti

p theo:
…
Bc k
: C
B
n c
;
vào
k
f
0
−1
và f
k-1
*
, b

t f
k-1
nh

ng b

1 l

ng

*
k k k
f x f f
−1 −1 −1
≥ − ∆

Nghi

m cu

i cùng c

a bài toán này l
#
y làm nghi

m cho bài toán ban

u.
1.3.2. Phng pháp th"a hi#p c$a TAMM
Gi

i bài toán:

(
)
{
}
x D
min F x

s
%
các nghi

m t

i

u
t

ng
;
ng là
(
)
i
x , i ,k
= 1
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 17 -
&
t M
i
= f
i
(x
i
).

ng

i chung

Bc 2
. Gi

i bài toán: min W
i
ii
M
xfM )(−

≤
W (
∀
i=
1,k
) x
∈
D
T
=


ó tìm

c nghi

m t

ng pháp này các hàm m

c tiêu

c s

p x

p d
"
a trên th
;
t
"
dãy
tiêu chu
K
n { f
1
…, f
k
}.



ây th
;
t
"
c

c.
Thu

t toán :

Bc 0
. S

p x

p th
;
t
"
các m

c tiêu theo

quan tr
'
ng

d

c dãy tiêu
chu
K
n f
1
,…,f

D
1

Bc 2
. Gi

i bài toán :
2
min
x D
f ( x )
∈

Ký hi

u:
{
}
2 2 2
2 2
x D
D x | f ( x ) min f ( x )
∈
= =
Ta có
D
⊇
D
1


D
1

⊇
…
⊇
D
k
.
Khi

ó, nghi

m c

a bài toán

b
<
c
k
là nghi

m c

a bài toán ban

u.
1.3.4. Thu't toán thích nghi n %nh ti u hoá vect
Bài toán t

n

t

t x
#
u c

a
x
theo ngh
@
a nào

ó.
Ta xét bài toán :

(
)
{
}
x D
max F x
∈

v
<
i các ràng bu

c 0 1

i. Yêu c

u ng
$
i
nh

n l
$
i gi

i
<
c l

ng giá tr

mà mình thích nh
#
t:
f
0
v
, (
kv ,1=
)
v
<
i


a:

kvxffE
v
v
,1,0)}({
0
==−Dx
xffE
v
v
∈
→− min})({
0&
t

l

ch:
kvxffxf
v
vv
v
,1)())((

v
v
xffE
1
20
min}))({(
α


ây:

=
=>
k
v
vv
1
1;0
αα

(ký hi

u
E
là k
L
v

J
ng trên
D
có m

t hàm ý thích. Còn quan h

tr

i

c
rút ra thông qua vi

c so sánh các hàm m

c tiêu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 20 -
CHNG 2


c tiêu, nh

ng nói chung th
$
ng qua hai b
<
c chính:

Tìm t

p các ph

ng án t

i

u Pareto

X
%
lý, thu g
'
n t

p t

i

u Pareto


{
}
x D
min( max ) F x
∈
( 2.1)
V
<
i các ràng bu

c 0 1
i
g ( x ) , x D ,i , ,m
≥ ∈ =

Trong

ó:
n
D ⊆

, là mi
!
n các ph

ng án ch
#
p nh

n

t s

k
C
thu

t s
%
d

ng gi

i thu

t di
truy
!
n

gi

i bài toán

a m

c tiêu theo h
<
ng quy v
!
m

o nh
#
t, h

p lí nh
#
t và t
"
nó

ã mang tính t

i

u. Quan ni

m này
có th



c xem nh

m

t tiên
!


úng, không ch

h

sau
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 21 -
bao gi
$
c
?
ng t

t h

n (phát tri

n h

n, hoàn thi

n h

n) th

h

tr
<
c. Xuyên su

t


n: sinh s

n và ch
'
n l
'
c t
"
nhiên, m
I
i cá th


mu

n t

n t
,
i và phát tri

n ph

i thích nghi v
<
i môi tr
$
ng, cá th


(NST), m
I
i NST
g

m nhi
!
u gen liên k

t v
<
i nhau theo c
#
u trúc d
,
ng chu
I
i, quy

nh các tính
tr
,
ng c

a cá th



ó. Các cá th


t
gi

a các cá th

trong cùng loài và quy

t

nh s
"
s

ng còn c

a cá th



ó. Do môi
tr
$
ng t
"
nhiên luôn bi

n

i nên c
#

trao

i thông tin có tính ng
D
u nhiên v
<
i môi tr
$
ng bên ngoài ho
&
c gi

a
các NST v
<
i nhau.
T
=
ý t

ng

ó, các nhà khoa h
'
c

ã nghiên c
;
u và xây d
"

mô ph

ng b

n quá trình c

b

n c

a t
"
nhiên: lai ghép,

t bi

n, sinh s

n và ch
'
n
l
'
c t
"
nhiên. M
I
i cá th



p t

bào m
I
i cá th

ch
F
có m

t NST. Các NST

c chia nh

thành các gen

c s

p x

p theo m

t dãy tuy

n tính. M
I
i cá th


(hay NST) bi

m l
$
i gi

i trong không gian l
$
i
gi

i c

a bài toán. Quá trình tìm ki

m ph

i
,
t

c hai m

c tiêu:

Khai thác nh

ng l
$
i gi

i t

trên m

t
cá th

, h

n n

a GA d
"
a vào quy lu

t ti

n hóa t
"
nhiên

tìm ra l
$
i gi

i do

ó
GA là gi

i thu


i

u

a m

c tiêu theo h
<
ng quy v
!
m

t
m

c tiêu thì ch
'
n GA làm công c

tính toán là thích h

p. Vì v

y, tr
<
c tiên ta s
E

tìm hi


2.1.1. C ch th+c hi#n gii thu't di truy*n
M

t thu

t gi

i di truy
!
n (hay m

t ch

ng trình ti

n hóa b
#
t k
L
)

gi

i m

t
bài toán c

th


Cách kh

i t
,
o qu

n th

ban

u.

M

t hàm l

ng giá

óng vai trò môi tr
$
ng



ánh giá các l
$
i gi

i
theo m

#
t áp d

ng các phép toán
di truy
!
n).
GA s
E
th
"
c hi

n ti

n trình tìm ki

m l
$
i gi

i t

i

u theo nhi
!
u h
<
ng, b


n hóa:

m
I
i th

h

s
E
t
,
o
ra các cá th

m
<
i b
J
ng cách lai ghép các cá th



ã có và

t bi

n chúng theo m


ng

i “x
#
u” thì ch

t

i, t
,
o ra th

h

m
<
i t

t h

n th

h

tr
<
c.
C
#
u trúc c

i t

o ng

u nhiên qu

n th

P(t);


ánh giá

phù h

p t

ng cá th

trong P(t);
Repeat
t:=t +1;
Ch

n các cá th

t

P(t - 1);
Lai t


p P(t);
Until (tho



i
!
u ki

n d
=
ng);
End;
Gi

i thích:
T
,
i l

n l
&
p th
;
t, GA xác

nh m

t t


m g
'
i là kích c
G
qu

n
th

). M
I
i l
$
i gi

i x
t
i


c

ánh giá nh
J
m xác

nh

phù h

i phù h

p
h

n. M

t s

ph

n t
%
c

a t

p h

p này

c tái s

n xu
#
t thông qua lai ghép và

t
bi



ó.
Nh

v

y, b

n ch
#
t GA là m

t gi

i thu

t l
&
p, nh
J
m gi

i quy

t các bài toán tìm
ki

m d
"
a trên c

c vào ho
,
t

ng c

a các NST và quá
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên