art3.ps

其中提到遺傳學的程式碼與應用提供給次淚相向的研究者參考下載

(e)225 565 y(able)j(to)g(unscrew)i(it)e(again.)24 b(Armed)16
b(with)g(just)g(a)g(hammer,)e(ev)o(erything)j(lo)q(oks)f(lik)o(e)225
615 y(a)g(nail.)25 b(Similarl)o(y)m(,)13 b(armed)j(with)g(only)g(a)g
(small)e(subset)k(of)d(classic)i(problem-solving)225
665 y(tec)o(hniques,)g(all)d(cost)i(functions)g(are)g(magicall)o(y)d
(transformed)i(in)o(to)f(smo)q(oth,)h(linear,)225 715
y(con)o(v)o(ex)f(mappings,)e(and)h(ev)o(ery)i(mo)q(del)d(is)i
(optimized)e(in)i(ligh)o(t)e(of)i(the)g(mean)f(squared)225
765 y(error.)37 b(This)20 b(results)h(in)e(\\p)q(erfect")j(answ)o(ers)f
(that)f(ha)o(v)o(e)f(questionable)h(relev)n(ance.)225
814 y(Understanding)14 b(when)f(the)g(decision)g(mak)o(er's)f(purp)q
(ose)i(should)e(or)h(shouldn't)g(b)q(e)g(ap-)225 864
y(pro)o(ximated)e(b)o(y)h(linearization)g(and)g(other)i(simplifyi)o(ng)
c(tec)o(hniques)k(is)e(of)g(paramoun)o(t)225 914 y(imp)q(ortance.)30
b(F)m(ormalizing)15 b(sub)r(jectiv)o(e)20 b(purp)q(ose)f(in)f(ob)r
(jectiv)o(e)g(measurable)g(terms)225 964 y(so)f(that)g(y)o(ou)g(can)h
(iden)o(tify)e(imp)q(ortan)o(t)f(di\013erences)20 b(b)q(et)o(w)o(een)e
(appro)o(ximations)d(and)225 1014 y(realit)o(y)f(is)h(a)g(c)o
(hallenging)f(task)h(that)h(requires)g(practice.)23 b(There's)16
b(no)f(substitute)h(for)225 1064 y(this)e(exp)q(erience.)300
1113 y(In)g(general,)g(real-w)o(orld)f(problems)g(are)h(di\016cult)f
(to)h(solv)o(e)f(for)h(sev)o(eral)g(reasons:)255 1188
y(1.)20 b Fk(The)g(numb)n(er)g(of)g(p)n(ossible)g(solutions)g(in)g(the)
g(se)n(ar)n(ch)f(sp)n(ac)n(e)i(is)e(so)h(lar)n(ge)g(as)g(to)308
1238 y(forbid)14 b(an)i(exhaustive)f(se)n(ar)n(ch)g(for)f(the)h(b)n
(est)g(answer.)308 1303 y Fl(Let)d(us)g(consider)h(an)e(elemen)o(tary)g
(problem)f(in)i(logic:)k(the)c(Bo)q(olean)f(satis\014abilit)o(y)308
1352 y(problem,)16 b(where)i(the)g(task)f(is)g(to)g(mak)o(e)e(a)i(comp)
q(ound)f(statemen)o(t)h(of)f(Bo)q(olean)308 1402 y(v)n(ariables)h(ev)n
(aluate)h(to)g(TR)o(UE.)g(F)m(or)f(example,)h(in)f(the)i(follo)o(wing)d
(problem)g(of)308 1452 y(100)d(v)n(ariables)g(giv)o(en)h(in)f
(conjunctiv)o(e)h(normal)e(form:)399 1531 y Fj(F)6 b
Fl(\()p Fj(x)p Fl(\))11 b(=)h(\()p Fj(x)583 1537 y Fi(17)627
1531 y Fh(_)p 664 1508 24 2 v 9 w Fj(x)688 1537 y Fi(37)732
1531 y Fh(_)d Fj(x)793 1537 y Fi(73)828 1531 y Fl(\))h
Fh(^)f Fl(\()p 907 1508 V Fj(x)930 1537 y Fi(11)975 1531
y Fh(_)p 1012 1508 V 9 w Fj(x)1035 1537 y Fi(56)1071
1531 y Fl(\))g Fh(^)g Fj(:)e(:)g(:)e Fh(^)754 1581 y
Fl(\()p Fj(x)794 1587 y Fi(2)821 1581 y Fh(_)k Fj(x)882
1587 y Fi(43)926 1581 y Fh(_)p 963 1558 V 9 w Fj(x)987
1587 y Fi(77)1031 1581 y Fh(_)p 1068 1558 V 9 w Fj(x)1092
1587 y Fi(89)1136 1581 y Fh(_)p 1173 1558 V 9 w Fj(x)1197
1587 y Fi(97)1232 1581 y Fl(\),)308 1660 y(the)15 b(c)o(hallenge)g(is)f
(to)h(\014nd)f(the)h(truth)h(assignmen)o(t)d(for)h(eac)o(h)h(v)n
(ariable)f Fj(x)1472 1666 y Fg(i)1485 1660 y Fl(,)h(for)f(all)308
1710 y Fj(i)20 b Fl(=)g(1)p Fj(;)7 b(:)g(:)g(:)e(;)i
Fl(100)17 b(suc)o(h)i(that)g Fj(F)6 b Fl(\()p Fj(x)p
Fl(\))19 b(=)g(TR)o(UE.)f(The)i(size)f(of)f(the)i(searc)o(h)g(space)308
1760 y(is)d(2)374 1745 y Fi(100)443 1760 y Fh(\031)h
Fl(10)535 1745 y Fi(30)569 1760 y Fl(.)29 b(W)m(e)16
b(ha)o(v)o(e)i(t)o(w)o(o)e(c)o(hoices)j(for)e(eac)o(h)g(v)n(ariable,)g
(and)g(tak)o(en)h(o)o(v)o(er)308 1809 y(100)f(v)n(ariables,)g(this)h
(generates)h(2)868 1794 y Fi(100)937 1809 y Fl(p)q(ossibilities.)28
b(This)18 b(is)f(a)g(h)o(uge)h(n)o(um)o(b)q(er!)308 1859
y(T)m(rying)e(out)h(all)f(of)g(these)i(alternativ)o(es)f(is)g(out)g(of)
f(the)i(question.)27 b(If)17 b(w)o(e)g(had)g(a)308 1909
y(computer)c(that)g(could)g(test)i(1000)d(strings)i(p)q(er)g(second)g
(and)f(could)g(ha)o(v)o(e)h(started)308 1959 y(using)h(this)h(computer)
f(at)h(the)g(b)q(eginning)f(of)g(time)f(itself,)h(15)g(billion)e(y)o
(ears)k(ago)308 2009 y(righ)o(t)c(at)h(the)g(Big)f(Bang,)g(w)o(e'd)h
(ha)o(v)o(e)f(examined)g(few)o(er)h(than)g(one)f(p)q(ercen)o(t)j(of)d
(all)308 2058 y(the)i(p)q(ossibilities)e(b)o(y)g(no)o(w.)308
2123 y(Note)f(that)g(the)g(real)f(problems)g(are)h(m)o(uc)o(h)e(more)g
(complex)h(than)g(that!)17 b(V)m(ariables)308 2173 y(are)f(not)f
(binary)g(and)h(their)g(n)o(um)o(b)q(er)f(is)g(often)h(greater)g(than)g
(10,000.)21 b(F)m(or)15 b(suc)o(h)308 2223 y(problems)20
b(with)g Fj(n)h Fl(v)n(ariables,)g(eac)o(h)g(dimension)f(can)h(con)o
(tain)f(an)g(in\014nit)o(y)g(of)p 225 2371 1423 2 v 225
2433 2 62 v 239 2412 a Fk(art2:)f(submitte)n(d)14 b(to)h
Fp(W)l(orld)g(Scien)o(ti\014)o(c)d Fk(on)k(June)f(1,)g(2000)389
b Fp(2)p 1646 2433 V 225 2435 1423 2 v eop
%%Page: 3 3
3 2 bop 308 267 a Fl(p)q(ossible)14 b(v)n(alues,)f(so)g(w)o(e)h(ha)o(v)
o(e)f(an)g(in\014nitely)g(large)g(space.)19 b(But)14
b(on)f(a)g(computer,)308 316 y(ev)o(erything)k(is)g(digital)e(and)i
(\014nite,)g(so)g(if)f(w)o(e)h(w)o(ere)h(going)e(to)h(implem)o(en)o(t)e
(some)308 366 y(sort)i(of)f(algorithm)f(to)h(\014nd)h(the)h(optim)o(um)
13 b(of)j(n)o(umerical)f(functions)i(with)g(real)308
416 y(parameter)10 b(v)n(alues)g(w)o(e'd)g(ha)o(v)o(e)g(to)g(consider)h
(the)g(a)o(v)n(ailable)d(computing)h(precision.)308 466
y(If)15 b(our)h(precision)g(guaran)o(teed)h(six)e(decimal)f(places,)j
(eac)o(h)f(v)n(ariable)e(could)i(then)308 516 y(tak)o(e)j(on)f
(10,000,000)e(di\013eren)o(t)j(v)n(alues.)32 b(Th)o(us)19
b(the)g(size)g(of)f(the)h(searc)o(h)h(space)308 565 y(w)o(ould)c(b)q(e)
i Fh(jS)s(j)e Fl(=)h(10000000)777 550 y Fg(n)814 565
y Fl(=)g(10)905 550 y Fi(7)p Fg(n)943 565 y Fl(.)27 b(That)17
b(n)o(um)o(b)q(er)f(is)h(m)o(uc)o(h)f(m)o(uc)o(h)g(larger)308
615 y(than)g(the)g(n)o(um)o(b)q(er)f(of)g(solutions)g(for)g(the)h(tra)o
(v)o(eling)f(salesman)f(problem.)22 b(Ev)o(en)308 665
y(for)12 b Fj(n)g Fl(=)f(50)h(there)i(are)f(10)719 650
y Fi(350)782 665 y Fl(solutions)f(to)g(a)h(nonlinear)e(programming)e
(problem)308 715 y(with)17 b(only)g(six)g(decimal)f(places)i(of)f
(precision.)1072 700 y Fg(a)1121 715 y Fl(Most)g(computers)h(could)f
(giv)o(e)308 765 y(t)o(wice)d(this)g(precision.)255 854
y(2.)20 b Fk(The)e(pr)n(oblem)g(is)f(so)h(c)n(omplic)n(ate)n(d)g(that)g
(just)g(to)g(facilitate)f(any)i(answer)e(at)h(al)r(l,)308
904 y(we)f(have)i(to)e(use)h(such)h(simpli\014e)n(d)e(mo)n(dels)h(of)f
(the)h(pr)n(oblem)f(that)h(any)g(r)n(esult)f(is)308 954
y(essential)r(ly)e(useless.)308 1024 y Fl(Ev)o(ery)d(time)f(w)o(e)h
(solv)o(e)f(a)h(problem)e(w)o(e)i(m)o(ust)f(realize)h(that)g(w)o(e)g
(are)g(in)f(realit)o(y)h(only)308 1073 y(\014nding)d(the)i(solution)d
(to)i(a)g Fk(mo)n(del)f Fl(of)g(the)i(problem.)k(All)9
b(mo)q(dels)f(are)j(a)e(simpli\014ca-)308 1123 y(tion)j(of)h(the)g
(real)g(w)o(orld,)f(otherwise)i(they)g(w)o(ould)e(b)q(e)i(as)f(complex)
f(and)g(un)o(wieldy)308 1173 y(are)j(the)g(natural)f(setting)h(itself.)
k(The)c(pro)q(cess)i(of)c(problem)h(solving)f(consists)i(of)308
1223 y(t)o(w)o(o)e(general)h(separate)h(steps:)k(\(1\))13
b(creating)h(a)f(mo)q(del)f(of)h(the)i(problem,)c(and)j(\(2\))308
1273 y(using)g(that)g(mo)q(del)e(to)i(generate)h(a)e(solution:)399
1362 y(Problem)g Fh(\))g Fl(Mo)q(del)h Fh(\))g Fl(Solution.)308
1452 y(So)g(the)i(\\solution")d(is)i(only)e(a)i(solution)f(in)g(terms)g
(of)g(the)h(mo)q(del.)k(If)c(our)f(mo)q(del)308 1502
y(has)h(a)g(high)f(degree)i(of)f(\014delit)o(y)f(then)i(w)o(e)f(can)g
(ha)o(v)o(e)g(more)f(con\014dence)j(that)e(our)308 1551
y(solution)20 b(will)f(b)q(e)i(meaningful.)35 b(In)21
b(con)o(trast,)h(if)e(the)h(mo)q(del)e(has)h(to)q(o)h(man)o(y)308
1601 y(unful\014lled)15 b(assumptions)g(and)h(rough)f(appro)o
(ximations,)f(the)i(solution)f(ma)o(y)f(b)q(e)308 1651
y(meaningless,)e(or)i(w)o(orse.)308 1721 y(In)h(general,)f(there)i(are)
f(t)o(w)o(o)f(p)q(ossible)h(approac)o(hes.)21 b(The)16
b(\014rst)f(uses)h(an)e(appro)o(x-)308 1771 y(imate)i(mo)q(del)g
Fj(M)5 b(odel)672 1777 y Fg(a)710 1771 y Fl(of)16 b(a)i(problem,)e(and)
h(then)i(\014nds)f(the)g(precise)h(solution)308 1820
y Fj(S)r(ol)q(ution)466 1826 y Fg(p)486 1820 y Fl(\()p
Fj(M)5 b(odel)620 1826 y Fg(a)641 1820 y Fl(\))14 b(for)f(this)h(appro)
o(ximate)e(mo)q(del:)399 1910 y(Problem)h Fh(\))g Fj(M)5
b(odel)739 1916 y Fg(a)774 1910 y Fh(\))13 b Fj(S)r(ol)q(ution)987
1916 y Fg(p)1007 1910 y Fl(\()p Fj(M)5 b(odel)1141 1916
y Fg(a)1162 1910 y Fl(\).)308 1999 y(The)16 b(second)h(approac)o(h)f
(uses)h(a)e(precise)j(mo)q(del)c Fj(M)5 b(odel)1220 2005
y Fg(p)1255 1999 y Fl(of)15 b(the)h(problem,)f(and)308
2049 y(then)k(\014nds)f(an)g(appro)o(ximate)e(solution)h
Fj(S)r(ol)q(ution)1135 2055 y Fg(a)1157 2049 y Fl(\()p
Fj(M)5 b(odel)1291 2055 y Fg(p)1310 2049 y Fl(\))18 b(for)g(this)g
(precise)308 2099 y(mo)q(del:)p 225 2145 558 2 v 225
2171 a Ff(a)244 2183 y Fm(Whereas)6 b(there)h(are)f Fe(\031)j
Fm(100,000,00)o(0,00)o(0,0)o(00,)o(000)o(,00)o(0,0)o(00,0)o(00)o(,000)o
(,00)o(0,0)o(00,)o(000)o(,00)o(0,00)o(0,0)o(00,)o(000)o(,00)o(0,0)o
(00,0)o(00)o(,000)225 2223 y(p)q(ossible)h(solutions)f(for)i(a)g
(50-cit)o(y)f(TSP)m(.)p 225 2371 1423 2 v 225 2433 2
62 v 239 2412 a Fk(art2:)19 b(submitte)n(d)14 b(to)h
Fp(W)l(orld)g(Scien)o(ti\014)o(c)d Fk(on)k(June)f(1,)g(2000)389
b Fp(3)p 1646 2433 V 225 2435 1423 2 v eop
%%Page: 4 4
4 3 bop 399 267 a Fl(Problem)13 b Fh(\))g Fj(M)5 b(odel)739
273 y Fg(p)773 267 y Fh(\))13 b Fj(S)r(ol)q(ution)986
273 y Fg(a)1007 267 y Fl(\()p Fj(M)5 b(odel)1141 273
y Fg(p)1161 267 y Fl(\).)308 345 y(Of)33 b(these)h(t)o(w)o(o)e(approac)
o(hes,)38 b(the)c(latter)f(one)g(is)f(often)h(sup)q(erior,)38
b(i.e.,)308 394 y Fj(S)r(ol)q(ution)466 400 y Fg(a)487
394 y Fl(\()p Fj(M)5 b(odel)621 400 y Fg(p)641 394 y
Fl(\))18 b(is)g(b)q(etter)i(than)f Fj(S)r(ol)q(ution)1109
400 y Fg(p)1129 394 y Fl(\()p Fj(M)5 b(odel)1263 400
y Fg(a)1284 394 y Fl(\),)19 b(as)f(a)g(solution)f(of)308
444 y(the)e(original)d(problem.)255 522 y(3.)20 b Fk(The)11
b(evaluation)h(function)f(that)h(describ)n(es)e(the)h(quality)g(of)g
(any)h(pr)n(op)n(ose)n(d)g(solution)308 572 y(is)17 b(noisy)h(or)g
(varies)f(with)g(time)g(ther)n(eby)g(r)n(e)n(quiring)g(not)h(just)f(a)h
(single)g(solution)308 622 y(but)d(an)g(entir)n(e)g(series)f(of)h
(solutions.)308 686 y Fl(F)m(or)g(example,)f(supp)q(ose)j(y)o(ou)e(are)
g(the)i(o)o(wner)e(of)g(a)g(ma)r(jor)f(sup)q(ermark)o(et)i(c)o(hain.)
308 736 y(Y)m(ou)k(need)h(to)e(decide)i(where)h(to)e(place)g(a)g(new)g
(store,)i(so)e(y)o(ou)g(calculate)g(the)308 785 y(cost)e(of)f
(construction)h(in)f(eac)o(h)h(p)q(ossible)g(lo)q(cation,)f(the)h
(demographics)e(of)h(the)308 835 y(neigh)o(b)q(oring)11
b(areas,)h(the)g(existing)f(comp)q(etition,)f(etc.,)i(form)o(ulate)d
(an)i(ev)n(aluation)308 885 y(function,)h(whic)o(h)h(w)o(ould)f(lik)o
(ely)g(result)i(in)e(a)h(nonlinear)f(programming)e(problem,)308
935 y(and)16 b(set)g(out)g(to)g(decide)h(where)f(the)h(b)q(est)g(place)
f(for)f(the)i(store)f(is.)24 b(But)17 b(there's)308 985
y(more)d(to)g(the)h(problem:)j(As)d(y)o(ou)f(are)h(deciding)f(where)i
(to)e(put)h(y)o(our)f(new)h(store,)308 1034 y(y)o(our)h(comp)q(etition)
f(is)i(an)o(ticipating)e(where)j(y)o(ou)e(will)f(put)h(this)h(store)g
(to)q(o,)g(and)308 1084 y(they)i(ha)o(v)o(e)f(their)h(o)o(wn)g(new)g
(store)g(to)f(construct.)34 b(They)19 b(are)g(activ)o(ely)f(trying)308
1134 y(to)f(\014gure)g(out)g(ho)o(w)f(b)q(est)i(to)f(place)g(their)h
(new)f(store)h(so)f(as)g(to)f(minimi)o(ze)f(y)o(our)308
1184 y(success.)20 b(If)14 b(y)o(ou)f(only)g(solv)o(e)g(the)h(problem)e
(of)h(the)i(b)q(est)f(p)q(osition)f(for)g(y)o(our)h(store)308
1234 y(giv)o(en)h(the)g(curren)o(t)i(conditions,)e(y)o(ou)f(are)i
(treating)f(the)h(situation)e(as)i(if)e(it)h(w)o(ere)308
1284 y(a)f(one-pla)o(y)o(er)h(game.)k(The)c(real-w)o(orld)f(problem)g
(often)g(c)o(hanges)i(while)e(y)o(ou)g(are)308 1333 y(deriving)g(a)g
(solution,)g(and)g(sometimes)f(it)i(c)o(hanges)g(in)f(w)o(a)o(ys)g
(that)h(are)g(designed)308 1383 y(to)f(mak)o(e)e(y)o(our)i(life)f
(di\016cult.)255 1461 y(4.)20 b Fk(The)d(p)n(ossible)h(solutions)f(ar)n
(e)g(so)h(he)n(avily)g(c)n(onstr)n(aine)n(d)f(that)h(c)n(onstructing)f
(even)308 1511 y(one)f(fe)n(asible)f(answer)g(is)g(di\016cult,)f(let)h
(alone)h(se)n(ar)n(ching)f(for)g(an)g(optimum)h(solu-