pareto (1121218), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

. .} be the corresponding Markov chain,at temperature c. The SAA is said to converge with probability 1 iflim lim IP{X k (c) ∈ P ∗ } = 1.c0 k→∞The next theorem, which is the main result in this paper, is an extension to MOPsof the results presented in Aarts and Korst (1989). Here we use ideas similar tothose in that paper, with the appropriate changes.In the proof of this theorem we show that the algorithm converges to the setopt ⊆ P ∗ , because of the particular transition probability we use.Theorem 1 Let P(c) be as in Definition 2 and, moreover, suppose that G(c) isirreducible.

Then:(a) The Markov chain has a stationary distribution q(c), whose components aregiven by df(i)1sqi (c) =exp − s=1∀i ∈ S,(8)N0 (c)cwhereN0 (c) =j∈S ds=1 f s ( j)exp −c(9)(b) For each i ∈ Sqi∗ := lim qi (c) =c01χ (i),|opt | optwhere |opt | denotes the number of elements in opt .(c) The SAA converges with probability 1.These results remain valid if (4) is replaced with (3).Before presenting the proof of Theorem 1 we state some preliminary results.First, we note the following fact, which is due to a + = a + (−a)+ (= a + a − ).Lemma 1 For any real numbers a1 , a2 , . .

. , an , b1 , b2 , . . . , bn , d+ d+d(ak − bk ) +(bk − ak )=(ak − bk ),k=1dk=1d(ak − bk ) +k=1k=1k=1d(bk − ak )+ =(ak − bk )+ .k=1We will need some properties of the limiting distribution, which we will presentnext. Recall that a probability distribution q is called the limiting distribution of aMarkov chain with transition probability P ifqi = lim IP(X k = i|X 0 = j) for all i, j ∈ S.k→∞Asymptotic convergence of a simulated annealing algorithm359If such a limiting distribution q exists and ai (k) = IP(X k = i), for i ∈ S, denotesthe distribution of X k , thenklim ai (k) = qi for all i ∈ S.→∞Moreover, q is an invariant (or stationary) distribution of the Markov chain,which means thatq = q P;(10)that is, q is a left eigenvector of P with eigenvalue 1. A converse to this result(which is true for finite Markov chains) is given in Lemma 3 below.Observe that (10) trivially holds if q is a probability distribution satisfyingqi Pi j = q j P ji ∀i,j ∈ S.(11)Equation (11) is called the detailed balance equation, and (10) is called theglobal balance equation.It is well known that in an irreducible Markov chain all of the states have thesame period.

This observation yields the following.Lemma 2 An irreducible Markov chain with transition matrix P is aperiodic ifthere exists j ∈ S such that P j j > 0.Lemma 3 (Lawler 1995, p. 19) Let P be the transition matrix of a finite, irreducibleand aperiodic Markov chain. Then the chain has a unique stationary distributionq, that is q is the unique distribution that satisfies (10), and, in addition, q is thechain’s limiting distributionProof of Theorem 1(a) Since G is irreducible, using Lemma 2 it can be seen that the Markov chain isirreducible and aperiodic (see Aarts and Korst 1989, p.39).

Hence, by Lemma3 there exists a unique stationary distribution. We now use (2) and (5) to seethat (11) holds for all i = j. First note thatqi (c)Pi j (c) = qi (c)G i j (c)Ai j (c)1q (c)Ai j (c) if j ∈ Si= i0if j ∈ Si .Similarly,q j (c)P ji (c) = q j (c)G ji (c)A ji (c)1q (c)A ji (c) if i ∈ S j= j0if i ∈ S j .Thus, since i ∈ S j if and only if j ∈ Si , to obtain (11) we only have to provethatqi (c)Ai j (c) = q j A ji (c).360M.

Villalobos-Arias et al.But this follows from (4), (8) and Lemma 1, becauseqi (c)Ai j (c) ddf s (i)( f s ( j) − f s (i))+1exp − s=1exp − s=1N0 (c)cc ddd+1s=1 f s ( j)s=1 ( f s (i) − f s ( j)) +s=1 ( f s ( j) − f s (i))=exp −exp −N0 (c)cc ddf s ( j)( f s (i) − f s ( j))+1exp − s=1=exp − s=1N0 (c)cc== q j (c)A ji (c).This shows that (11) holds, which in turn yields part (a) in Theorem 1.

(Note thatthis proof, with obvious changes, remains valid if the acceptance probability isgiven by (3) rather than (4)).(b) Note that for each a ≤ 01 if a = 0,lim ea/x =(12)0 otherwise.x0Now, by (6), (8) and (9) df (i)m − ds=1 f s (i)expexp − s=1c sc =qi (c) =dm − ds=1 f s ( j)s=1 f s ( j)exp−expj∈Sj∈Sccdm − s=1 f s (i)expc χopt (i) + χ S−opt (i)=dm − s=1 f s ( j)j∈S expc=j∈Sexpexp+1 χopt (i)m − ds=1 f s ( j)cm − ds=1 f s (i)cj∈Sexp χ S−opt (i).m − ds=1 f s ( j)cNow let c 0. Then, by (12), the second term of the latter sum goes to 0,whereas the denominator of the first term goes to |opt |. Hencelim qi (c) =c01χ (i) + 0 = qi∗ ,|opt | optwhich completes the proof of part (b).Asymptotic convergence of a simulated annealing algorithm361(c) By (b) and Lemma 3lim lim IP{X k = i} = lim qi (c) = qi∗ ,c0 k→∞c0and so by (7)lim lim IP{X k ∈ P ∗ } ≥ lim lim IP{X k ∈ opt } = 1.c0 k→∞c0 k→∞(13)Thuslim lim IP{X k ∈ P ∗ } = 1,c0 k→∞and (c) follows.5 Concluding remarksWe have shown in Theorem 1 that a suitable choice of the acceptance probabilities yields the asymptotic convergence of the SAA.

This is reassuring, of course,because it means that the algorithm is indeed heading in the right direction. However, for computational purposes, our approach might not be very useful.Fig. 2 Comparison of opt and P ∗Indeed, what we actually prove is that, as in (13), the underlying Markov chainconverges to the set opt which can be very “small” compared to the Pareto optimalset P ∗ .362M.

Villalobos-Arias et al.This is illustrated in Figure 2 in which the Pareto front corresponds to the partson the boundary of S joining the points A and B, and also the points C and D,whereas F(opt ) corresponds only to the points that give p1 and p2 .To improve our SAA one possibility would be to introduce an “elite set”, whichis a standard procedure in multiobjective evolutionary algorithms (Coello Coelloet al.

2002; Deb 2001). At each step of the algorithm, the elite set contains all thenondominated points generated so far. Thus, by introducing the elite set, the ideawould be to make the contents of such elite set to converge to the Pareto optimalset. Research along these lines is in progress.Acknowledgements The second author acknowledges support fom CONACyT through project42435-Y. The third author was partially supported by CONACyT Grant 45693.ReferencesAarts EH, Korst JH (1989) Simulated annealing and Boltzmann machines: a stochastic approachto combinatorial optimization and neural computing.

Wiley, ChichesterČerny V (1985) A thermodynamical approach to the traveling salesman problem: an efficientsimulation algorithm. J Optim Theory Appl 45(1):41–51Coello Coello CA, Van Veldhuizen DA, Lamont GB (2002) Evolutionary algorithms for solvingmulti-objective problems. Kluwer, New York, ISBN 0-3064-6762-3Deb K (2001) Multi-objective optimization using evolutionary algorithms.

Wiley, Chichester,ISBN 0-471-87339-XDowsland KA (1993) Simulated annealing. In: Reeves CR (ed) Modern heuristic techniques forcombinatorial problems, chapter 2. Wiley, pp 20–69Kirkpatrick S, Gellatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science220(4598):671–680Laarhoven P, Aarts EH (1987) Simulated annealing: theory and applications. D.

Reidel, BostonLawler GF (1995) Introduction to stochastic processes. Chapman & Hall/CRC, Boca RatonMetropolis N, Rosenbluth AW, Rosenbluth MN, Teller A, Teller E (1953) Equation of statecalculations by fast computing machines. J Chem Phys 21(6):1087–1092Rudolph G (1998) On a multi-objective evolutionary algorithm and its convergence to the paretoset. In: Proceedings of the 5th IEEE Conference on Evolutionary Computation. IEEE Press,Piscataway, pp 511–516Rudolph G, Agapie A (2000) Convergence properties of some multi-objective evolutionary algorithms. In: Proceedings of the 2000 conference on evolutionary computation, vol 2. IEEE Press,Piscataway, pp 1010–1016Sait SM, Youssef H (1999) Iterative computer algorithms with applications in engineering.

Solving combinatorial optimization problems. IEEE Computer Society, Los AlamitosSerafini P (1994) Simulated annealing for multiple objective optimization problems. In: TzengGH, Wang HF, Wen UP, Yu PL (eds) Proceedings of the 10th international conference onmultiple criteria decision making: expand and enrich the domains of thinking and application,vol 1.

Springer, Berlin Heidelberg New York, pp 283–292Ulungu EL (1993) Optimisation combinatoire multicritere: determination de l’ensemble dessolutions efficaces et methodes interactives. PhD Thesis, Faculté des Sciences, Université deMons-Hainaut, Mons, BelgiumUlungu EL, Teghem J, Fortemps Ph (1995) Heuristics for multi-objective combinatorial optimization by simulated annealing. In: Gu J, Chen G, Wei Q, Wang S (eds) Multiple criteria decisionmaking: theory and applications.

Proceedings of the 6th national conference on multiple criteriadecision making, Sci-Tech, Windsor, pp 228–238Ulungu EL, Teghem J, Ost Ch (1998) Efficiency of interactive multi-objective simulated annealing through a case study. J Oper Res Soc 49:1044–1050Ulungu EL, Teghem J, Fortemps Ph, Tuyttens D (1999) MOSA method: a tool for solving multiobjective combinatorial optimization problems. J Multi criteria Decis Anal 8(4):221–236.

Характеристики

Список файлов лекций