Application Of Genetic Algorithm And Neural Network To Layout Sub-Problem

Genetic Algorithm (GA) is a kind of self-adaptive, stochastic, global optimization method. To solve problem, GA deals with structural object directly without any requirements of differentiability and continuation of function; it's global, robust and parallel in working mode.Neural network (NN) is product of simulation of how-to-manage-information in human brain. Discrete Neural Network is presented and applied successfully to solve combinatorial problem by Hopfield in 1982. So far, the most popular NN used is BP network that not only has strong nonlinear mapping capability, but can realize relatively complex causality, and that bears advantages like self-adaptive, self-study and acceptance of errors.Layout problem is an important offshoot of Operation Research; it belongs to complex combinatorial optimization problem. Researches since 1970's show that we could hardly find a way that is complete, strict, and not so slow to solve NPC problem. In the nature of things, GA and NN are selected to solve combinatorial problem, and to seek some balance between speed and precision. Despite all that, fusing GA and NN together to obtain satisfactory solution of layout problem has large space for researchers and has practical meaning.In this paper, many efforts are made and some results are achieved as follows:1. An isomorphic non-overlap layout optimization algorithm is proposed. So long as given a non-overlap layout scheme, the algorithm can guarantee that new layout schemes produced are isomorphic with the given one.2. Research in basic theory of GA and its application are retrospected and a new mutation operator, combinational mutation, is defined. Then the author desigened an improved genetic algorithm for Isomorphic layout identification class (i.e., the sub-problem) after a manner to maintain the adjacent relation of graph elements. The algorithm presented can attain the global optimization layout scheme with relatively fast convergent speed.3. Neural network is applied to layout problem, and a feed-forward network of layout problem is proposed. Then a genetic neural network for layout sub-problem is produced with GA and NN integrated together. Given a set of rational training samples, good weights and thresholds were attained through the new algorithm; at the same time, the algorithm converged steadily to a better layout scheme. Numerical experiments show that it is feasible and effective.