J89 (1121213), страница 4

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

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

The latter result allows the original problem to be decomposed by its constraintsto multiple subproblems and to the reweighting of those violated global constraintsdefined by (19). The major benefit of this decomposition is that each subprobleminvolves only a fraction of the original constraints and is, therefore, a significant relaxation of the original problem with much lower complexity. The decomposition leadsto a large reduction in the complexity of the original problem if the global constraintsJ Glob OptimFig. 1 CSA constrained simulated annealing (see text for the initial values of the parameters).

Thedifferences between CSA and SA lie in their definitions of state z, neighborhood Nm (z), generationprobability G(z, z ), and acceptance probability AT (z, z )is small in quantity and can be resolved efficiently. We demonstrate in Sect. 5 that thenumber of global constraints in many benchmarks is indeed small when we exploit thelocality of the constraints. In the next section, we describe our extensions to simulatedannealing for finding ESPs.3 Simulated annealing for constrained optimizationIn this section, we present three algorithms for finding ESPs: the first two implementing the results in Theorems 1 and 2, and the third extending the penalty searchalgorithms in Sect.

2.1. All three methods are based on sampling the search space ofa problem during their search and can be applied to solve continuous, discrete, andmixed-integer optimization problems. Without loss of generality, we only consider Pmwith equality constraints, since an inequality constraint gj (z) ≤ 0 can be transformedinto an equivalent equality constraint gj (z)+ = 0.3.1 Constrained simulated annealing (CSA)Figure 1 presents CSA, our algorithm for finding an ESP whose (z∗ , α ∗∗ )T satisfies (13).

In addition to probabilistic descents in the z subspace as in SA [19], withan acceptance probability governed by a temperature that is reduced by a properlychosen cooling schedule, CSA also does probabilistic ascents in the penalty subspace.The success of CSA lies in its strategy to search in the joint z − α space, instead ofapplying SA to search in the z subspace of the penalty function and updating thepenalties in a separate phase of the algorithm. The latter approach would be takenin existing static and the dynamic penalty methods discussed in Section 2.1. CSAovercomes the limitations of existing penalty methods because it does not require aseparate algorithm for choosing penalties.

The rest of this section explains the stepsof CSA [29,31].Line 2 sets a starting point z ← (z, α)T , where z can be either user-provided orrandomly generated (such as using a fixed seed 123 in our experiments), and α isinitialized to zero.Line 3 initializes control parameter temperature T to be so large that almostany trial point z will be accepted. In our experiments on continuous problems, weJ Glob Optiminitialize T by first randomly generating 100 points of x and their correspondingneighbors x !∈ N c(x) in closeproximity, where |xi − xi | ≤ 0.001, and then settingTTT = maxx,x ,i |Lm (x , 1) − Lm (x, 1) |, |hi (x)| . Hence, we use a large initial T ifthe function is rugged (|Lm (x , 1)T − Lm (x, 1)T | is large), or the function is notrugged but its constraint violation (|hi (x)|) is large.

We also initialize κ to 0.95 in ourexperiments.Line 4 sets the number of iterations at each temperature. In our experiments, wechoose NT ← ζ (20n + m) where ζ ← 10(n + m), n is the number of variables, and mis the number of equality constraints. This setting is based on the heuristic rule in [10]using n + m instead of n.Line 5 stops CSA when the current z is not changed, i.e., no other z is accepted,in two successive temperature changes, or when the current T is small enough (e.g.,T < 10−6 ).Line 7 generates a random point z ∈ N m (z) from the current z ∈ S = Z × , where = Rm is the space of the penalty vector. In our implementation, N m (z) consists of(z , α)T and (z, α )T , where z ∈ N m1(z) (see Definition 1), and α ∈ N m2(α) is a pointneighboring to α when h(z) = 0: N m (z) = (z , α)T ∈ S where z ∈ N m (z) ∪ (z, α )T ∈ S where α ∈ N m2(α)1(21)and!N m2(α) = α ∈ where (αi < αi or αi > αi if hi (z) = 0)and (αi = αi if hi (z) = 0) .According to this definition, αi is not perturbed when hi (z) = 0 is satisfied.G(z, z ), the generation probability from z to z ∈ N m (z), satisfies:G(z, z ) = 1.0 ≥ G(z, z ) ≤ 1 and(22)(23)z ∈Nm (z)Since the choice of G(z, z ) is arbitrary as long as it satisfies (23), we select z in ourexperiments with uniform probability across all the points in N m (z), independent of T:G(z, z ) =1.|N m (z)|(24)As we perturb either z or α but not both simultaneously, (24) means that z is generated either by choosing z ∈ N m1(z) randomly or by generating α uniformly in apredefined range.Line 8 accepts z with acceptance probability AT (z, z ) that consists of two components, depending on whether z or α is changed in z :⎧⎨exp − (Lm (z )−Lm (z))+ ,if z = (z , α)T ,TAT (z, z ) =(25)⎩exp − (Lm (z)−Lm (z ))+ ,if z = (z, α )T .TThe acceptance probability in (25) differs from the acceptance probability used inconventional SA, which only has the first case in (25) and whose goal is to look for aglobal minimum in the z subspace.

Without the α subspace, only probabilistic descentsin the z subspace are carried out.J Glob OptimIn contrast, our goal is to look for an ESP in the joint Z × space, each existing ata local minimum in the z subspace and at a local maximum in the α subspace. To thisend, CSA carries out probabilistic descents of Lm (z, α)T with respect to z for eachfixed α. That is, when we generate a new z under a fixed α, we accept it with probability one when δz = Lm (z , α)T − Lm (z, α)T is negative; otherwise, we accept itwith probability e−δz /T .

This step has exactly the same effect as in conventional SA;that is, it performs descents with occasional ascents in the z subspace.However, descents in the z subspace alone will lead to a local/global minimumof the penalty function without satisfying the corresponding constraints. In order tosatisfy all the constraints, CSA also carries out probabilistic ascents of Lm (z, α)Twith respect to α for each fixed z in order to increase the penalties of violated constraints and to force them into satisfaction. Hence, when we generatea new α underTa fixed z, we accept it with probability one when δα = Lm (z, α ) − Lm (z, α)Tis positive; otherwise, we accept it with probability e−δα /T .

This step is the same asthat in conventional SA when performing ascents with occasional descents in the αsubspace. Note that when a constraint is satisfied, the corresponding penalty will notbe changed according to (22).Finally, Line 10 reduces T by the following cooling schedule after looping NT timesat given T:T ←− κ · Twhere the cooling-rate constant κ ← 0.95 (typically 0.8 ≤ κ ≤ 0.99).(26)At high T, (25) allows any trial point to be accepted with high probabilities, therebyallowing the search to traverse a large space and overcome infeasible regions.

WhenT is reduced, the acceptance probability decreases, and at very low temperatures, thealgorithm behaves like a local search.3.2 Constraint-partitioned simulated annealing (CPSA)We present in this section CPSA, an extension of CSA that decomposes the search inCSA into multiple subproblems after partitioning the constraints into subsets. Recallthat, according to Theorem 2, Pt in (14) can be partitioned into a sequence of Nsubproblems defined in (20) and an overall necessary condition defined in (19) onthe global constraints across the subproblems, after choosing an appropriate mixedneighborhood. Instead of considering all the constraints together as in CSA, CPSAperforms searches in multiple subproblems, each involving a small subset of the constraints.

As in CSA, we only consider Pt with equality constraints.Figure 2 shows the idea in CPSA. Unlike the original CSA that solves the problem as a whole, CPSA solves each subproblem independently. In Subproblem t, t =1, ..., N, CSA is performed in the (z(t), α(t))T subspace related to the local constraintsh(t) (z(t)) = 0. In addition, there is a global search that explores in the (z(g), γ )Tsubspace on the global constraints H(z) = 0.

This additional search is needed forresolving any violated global constraints.Figure 3 describes the CPSA procedure. The first six lines are similar to those inCSA.To facilitate the convergence analysis of CPSA in a Markov-chain model, Lines7–14 randomly pick a subproblem for evaluation, instead of deterministically enumerating the subproblems in a round-robin fashion, and stochastically accept a newJ Glob OptimFig. 2 CPSA Constraint-partitioned simulated annealing____Fig.

3 The CPSA search procedureprobe using an acceptance probability governed by a decreasing temperature. Thisapproach leads to a memoryless Markovian process in CPSA.Line 7 randomly selects Subproblem i, i = 1, . . . , N + 1, with probability Ps (t),where Ps (t) can be arbitrarily chosen as long as:N+1Ps (t) = 1 and Ps (t) > 0.(27)t=1When t is between 1 and N (Line 8), it represents a local exploration step in Sub(t)problem t. In this case, Line 9 generates a trial point z ∈ N p (z) from the currentT(t)point z = (z, α, γ ) ∈ S using a generation probability G (z, z ) that can be arbitraryas long as the following is satisfied:0 ≤ G(t) (z, z ) ≤ 1 and(t)z ∈Np (z)G(t) (z, z ) = 1.(28)J Glob Optim(t)The point is generated by perturbing z(t) and α(t) in their neighborhood N p (z):N p(t) (z) = (z , α(t), γ ) ∈ S | z ∈ N p(t) (z)1∪(z, α (t), γ ) ∈ S | α (t) ∈ N p(t) (α(t)) ,2N p(t) (α(t)) = α (t) ∈ (α(t)) where (αi (t) < αi (t) or αi (t) > αi (t) if hi (z(t)) = 0)2and (αi (t) = αi (t) if hi (z(t)) = 0)(t)(29)(30)(t)and N p (z) is defined in (15) and (α(t)) = Rmt .

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

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