Self-organizing Optimization With Extremal Dynamics: Theory, Algorithms, And Applications

Combinatorial optimization is the process of finding one or more optimal solutions in a well defined discrete configuration space, i.e., a space containing a finite set of possible solutions. Such problems occur frequently in the fields ranging from scientific computation to engineering practice, e.g., system control, artificial intelligence, production scheduling, transportation system, network communication, bioinformatics, and etc. As a discipline with both theoretical and practical values, combinatorial optimization theory and algorithms have been extensively studied by many researchers. Generally, some of combinatorial optimization problems are easy to handle with mathematical programming methods. But when the dimension of the solution space becomes huge, especially in real-world applications, those conventional optimization methods in operations research fail to find the optimum in a reasonable computation time. Consequently, the novel intelligent optimization methods are needed to deal with complex combinatorial optimization problems. This thesis presents the research results of extremal dynamics oriented self-organizing optimization from theory, algorithms to applications. The main topics studied in this thesis are as follows:Based on the concept of decentralized control, the thesis proposes the definitions of discrete state variable and local fitness function and further discusses the consistency and equivalence conditions between local fitness function and global objective function. To improve computation efficiency and develop better algorithms, in this work we present the analytical solution and experimental investigation of microscopic distribution on the combinatorial optimization solution. In view of the fact that worst-case and average-case complexity analysis can not capture well the actual computational complexity of typical problem instances encountered in practical applications, this thesis investigates the theory of"phase transition"for typical-case complexity analysis. In numerous constrained decision problems, the solution space of the relevant optimization problem is statistically analyzed from the characteristics of phase transition, and the computational complexity usually occurs on the boundary of phase transition. For analyzing and visualizing the solution space, we propose the novel concept of fitness network to characterize the structure of configuration space.Since the multi-particle systems in statistical physics have a deep and useful connection with multivariate or combinatorial optimization, e.g., finding the minimum cost solution in a combinatorial optimization problem is analogous to finding the lowest energy state in a physical system, the thesis presents a general-purpose self-organizing optimization method with extremal dynamics after studying and analyzing self-organizing sandpile model and Bak-Sneppen evolution model. In the proposed optimization dynamics, the states of those variables with comparatively high energy are updated successively. As a result, a sub-optimal solution can be quickly organized, and moreover, chaotic stochastic samplings of microstates near the optimal solution enable the search to effectively scaling barriers of fitness landscape and exploring local optima of configuration space. Theoretical analysis and numerical experiments on the NP-complete traveling salesman problem demonstrate that the proposed method outperforms other optimization techniques developed from statistical physics, such as simulated annealing, extremal optimization, and etc.In order to improve the limitations of evolutionary algorithms on theoretical foundations, local searching ability and computational complexity, the thesis explores a novel self-organizing evolutionary algorithm for finding high-quality solutions for those hard computational systems. This proposed method, so-called"gene optimization", successively eliminates extremely undesirable components of sub-optimal solutions based on the local fitness of the genes. A near-optimal solution can be quickly obtained by the self-organizing co-evolution process of computational systems. Since the evolutionary computation methodology under study takes the aim at the natures and micro-mechanisms of those hard computational systems, and guide the evolutionary optimization process at the level of genes, it may syncretize the two origins of evolution order: natural selection and self-organization, create much better evolutionary algorithms and affect the conceptual foundations of evolutionary computation.Since mcroarrays can identify thousands of genes simultaneously, microarray-based genomic analysis is becoming increasingly important in biology and bioinformatics. As an application of self-organizing optimization algorithm, this thesis attempts to solve the recently emerging microarray gene ordering problem. Given a matrix of the gene expression data values, the task of microarray gene ordering problem is to find a permutation of genes such that those genes with similar expression patterns should be relatively close in the permutation. In this work, the gene ordering problem is modeled as a shortest-path problem, and a self-organizing ordering algorithm is proposed for rearranging gene expression data in a linear order aiming to reveal trends in large amount of data. The effectiveness of the algorithm is demonstrated by the computational results on random 2-dimensional data, artificial data, and biological datasets.Hot strip mill (HSM) producing hot rolled finished products from steel slabs is one of the most important production lines in a steel plant. The functional task of a HSM production scheduling system is to construct a rolling sequence that optimizes a set of given criteria subject to predefined constraints. The HSM scheduling has become a challenge problem due to its complexity in optimization and computation. Based on the introduction to production process, relevant business requirements, and the analysis of the previous research and development on modeling and optimization for production scheduling solutions. The thesis presents the problem formulation and scheduling model, which is characterized by two major requirements: (i) selecting a subset of orders from manufacturing orders to be processed; (ii) determining the optimal production sequence under multiple constraints, such as sequence-dependant transition costs, non-execution penalties, earliness/tardiness (E/T) penalties, and etc. Due to its NP-hard complexity, in this work a hybrid optimization solution with an integration of genetic algorithm and self-organizing optimization is developed to solve the HSM scheduling problem. The simulation results with production scale data demonstrate that the proposed HSM scheduling solution can be applied in practice to provide satisfactory performance.