Solution space

Fig. 7. Heat-exchange network solution space (2), where line A represents the minimum utiUty for feasibiUty, ie, infinite area requited. Region B is the...

Like simulated annealing, tabu search is a technique designed to avoid the problem of becoming trapped in local optima. The procedure is basically hill-climbing, which commences at an initial solution and searches the neighbourhood for a better solution. However, the process will recognize, and avoid areas of the solution space that it has already encountered, thus making these areas tabu . The tabu moves are kept in a finite list, which is updated as the search proceeds. 

Now, to be sure, not every possible subset of the solution-space can be described as a schema. Simple counting shows that a length-A chromosome can have 2 possible configurations, and therefore 2 possible subsets, but only 3 different schemas. Nonetheless, it is a central axiom of the building-block hypothesis that it is precisely the set of schemas that are effectively being processed by GAs. 

The vertical reactor simulations reported In this paper typically Involved 14,000 unknowns and took 25 CPU seconds per Newton Iteration on a Cray-2. The tracing of a complete family of solutions for one parameter (e.g. susceptor temperature) cost approximately 25 CPU minutes. The latter number underscores the advantage of using supercomputers to understand the structure of the solution space for physical problems which often Involve many parameters. 

A. Solution Space Representation—Discrete Decision Process.555... 

An examination of previous classical learning procedures reveals that they differ from each other only with respect to the choices of /, and S. All of them share the same basic format for and the corresponding solution space, S. Let s assume that each (x, y) pair in the problem statement (2) contains a total of M decision variables ... 

Traditional approaches adopt a solution space S that coincides with decision) d thus any final solution or x ) has the same format as x, consisting of a real vector that defines a single point in the decision space. 

Since a real vector is a degenerate interval vector whose components are null width intervals, previous conventional pointwise solution formats can be considered a particular case of the suggested alternative and more general solution space, obtained when the minimum allowed region size is reduced to zero, thus converting hyperrectangles into single points. 

Solution format, The solution space consists of hyperrectangles ( == X G), instead of points ( = x g, ), defined in the decision space. 

A solution space, a, consisting of hyperrectangles defined in the decision space, X, is a basic characteristic common to all the learning methodologies that will be described in subsequent sections. The same does not happen with the specific performance criteria tfi, mapping models /, and search procedures 5, which obviously depend on the particular nature of the systems under analysis, and the type of the corresponding performance metric, y. 

The solution space thus consists of hyperrectangles in the decision space, X Gand the corresponding performanee criteria are the conditional probabilities of getting any given y value inside X,p(y= X), = 1,..., or the single most likely y value within X. 

For the reasons already discussed in Section III, our solution space consists of hyperrectangles in the decision space, X g I, not single points, X. The corresponding performance criterion used to evaluate solutions, i/i, is the expected y value within X ... 

The most important changes and adaptations that were introduced in order to handle such multiobjective problems are summarized in Table III. The solution space remains the same as for the single objective case. 

Representation. The solution space is composed of discrete combinatorial alternatives of batch production schedules. For example, in the permutation flowshop problem, where the batches are assumed to be executed in the same order on each unit, there are A number of solutions, where N is the number of batches. We must find a way to compactly represent this solution space, in such a way that significant portions of the space can be characterized with respect to our objective as either poor or good without explicitly enumerating them. 

The first step in solving a combinatorial optimization problem is to model the solution space itself. Such a model should be declarative in character, if it is to be independent of the characteristics of the specific algorithm that will be used to find the solution within the solution space. The model we have adopted for the scheduling of flowshop operations is the discrete decision process (DDP) introduced originally by Karp and Held (1967). As defined by Ibaraki (1978) a DDP, Y, is a triple (.S,S,/) with its elements defined as follows ... 

The large size of the solution space for combinatorial optimization problems forces us to represent it implicitly. The branch-and-bound algorithm encodes the entire solution space in a root node, which is successively expanded into branching nodes. Each of these nodes represents a subset of the original solution space specialized to contain some particular element of the problem structure. 

In the flowshop example, the subsets of the solution space consists of subsets of feasible schedules. We can organize these subsets in a variety of ways for example, fixing any one position of the N available positions in the schedule to be a particular batch creates N subsets of size iN - 1) . Subsequently, as we fix more and more of the positions, the sets will include fewer and fewer possibilities, until all the positions are fixed, and we have a single element in the set corresponding to a single, feasible schedule. 

Mutual exclusivity. In branching from one node to its descendants, we should ensure that none of the subsets overlap with one another otherwise we could potentially explore the same solution subsets in multiple branches of the tree. Formally, if X is the original solution space and x, is the ith subset, then... 

Having formally defined the branching structure, we must now make explicit the mechanisms by which we can eliminate subsets of the solution space from further consideration. Ibaraki (1978) has stated three major mechanisms for controlling the evolution of the branch-and-bound search algorithms, by eliminating potential solution through... 

A graphic technique may be obtained from the polynomial equations, as represented in Fig. 6. Figure 6a shows the contours for tablet hardness as the levels of the independent variables are changed. Figure 6b shows similar contours for the dissolution response, t50%. If the requirements on the final tablet are that hardness be 8-10 kg and t o% be 20-33 min, the feasible solution space is indicated in Fig. 6c. This has been obtained by superimposing Fig. 6a and b, and several different combinations of X and X2 will suffice. 

Fig. 6 Contour plots for the Lagrangian method (a) tablet hardness (b) dissolution (t50%) (c) feasible solution space indicated by crosshatched area. (From Ref. 15.)... 

Such problems can be overcome in a number of ways. The first way is by changing the model such that the solution space becomes more regular, making the optimization simpler. This most often means simplifying the mathematical model. A second way is by repeating the search many times, but starting each new search from a different initial location. A third way exploits mathematical transformations and bounding techniques for some forms of mathematical... 

One fundamental practical difficulty with both the direct and indirect search methods is that, depending on the shape of the solution space, the search can locate local optima, rather than the global optimum. Often, the only way to ensure that the global optimum has been reached is to start the optimization from different initial points and repeat the process. 

Now consider the influence of the inequality constraints on the optimization problem. The effect of inequality constraints is to reduce the size of the solution space that must be searched. However, the way in which the constraints bound the feasible region is important. Figure 3.10 illustrates the concept of convex and nonconvex regions. 

The feasible solution space can be represented graphically by plotting the above inequality constraints as equality constraints ... 

This is shown in Figure 3.12. The feasible solution space in Figure 3.12 is given by ABCD. 

Whilst Example 3.1 is an extremely simple example, it illustrates a number of important points. If the optimization problem is completely linear, the solution space is convex and a global optimum solution can be generated. The optimum always occurs at an extreme point, as is illustrated in Figure 3.12. The optimum cannot occur inside the feasible region, it must always be at the boundary. For linear functions, running up the gradient can always increase the objective function until a boundary wall is hit. 

---