Show description

Moreover, the probability distributions are chosen so that apj^^i(A) < apjJ^A). In this way, escaping local optima is relatively easy during the first iterations, and the procedure explores the set S freely. But, as the iteration count increases, only improving transitions tend to be accepted, and the solution path is likely to terminate in a local optimum. The procedure stops if the value of the objective function remains constant in L (a termination parameter) consecutive iterations, or if the number of iterations becomes too large.

G. ejection chains. Parts of this section can also be found embedded within a problem related setting in [CKP95,PG97]. e. e. the set of feasible solutions of the problem. One of the most intuitive solution approaches to this optimization problem is to start with a known feasible solution and slightly perturb it while decreasing the value of the objective function. In order to realize the concept of slight perturbation let us associate with every x a subset iV{x) of 5, called neighborhood of x. The solutions in iV{x), or neighbors of X, are viewed as perturbations of x.

To define another interesting class of graphs let us consider a finite set V and a collection {1^)^^^; of intervals /^ on the reals. This collection defines a partial order ^ on T^ as follows: V /^ is entirely before /^ . Such a partial order is called an interval order. Without loss of generality, we may assume that the intervals have the form [n^ n2) with n^ and n2 integral. 2) as an induced subgraph [Fis70]. 1 N-structured precedence graph. 2 Graph IK^. Finally we introduce a class of precedence graphs that has been considered frequently in literature.