Studies On Optimization Methods With Extremal Dynamics And Applications

In recent years, the studies on NP-hard combinatorial optimization problems have beena challenge subject in optimization community. In addition to traditional operations research,the modern heuristics have been attractive in fundamental research and real applications. Theapproaches to evolutionary algorithm (EA), artificial life, simulated annealing (SA) and Tabusearch et al. are developed from the natures of biological evolution, statistical physics andartificial intelligence et al..Recently, a novel general-purpose local search optimization approach, so-called"Ex-tremal Optimization (EO)"has been proposed based on the fundamentals of statisticalphysics. In contrast to SA which is inspired by equilibrium statistical physics, EO is basedon Bak-Sneppen (BS) model of biological evolution which simulates far-from equilibriumdynamics in statistical physics. The BS model is one of the models that show the natureof self-organized criticality (SOC). The SOC means that regardless of the initial state, thesystem always tunes itself to a critical point having a power-law behavior without any tun-ing control parameter. In contrast to genetic algorithms (GAs) which operate on an entire"gene-pool"of huge number of possible solutions, EO successively eliminates those worstcomponents in the sub-optimal solutions. The extremal dynamics mechanism in EO pro-vide significant hill-climbing ability, which enables EO to perform well particularly at thephase transitions. EO has many advanced features,such as fast convergence speed, strongability of local search, only mutation operator, no adjustable parameter for basic EO or onlyone adjustable parameterτforτ-EO. EO has been successfully applied to some NP-hardcombinatorial optimization problems such as graph bi-partitioning, traveling salesman prob-lem(TSP), graph coloring, spin glasses and dynamic combinatorial problems. However, sofar there have been only limited papers studying on the mechanism of EO applied to numer-ical optimization problems or multiobjective optimization problems(MOPs).This paper makes an investigation on the mechanism of EO for solving the uncon-strained or constrained numerical optimization problems, and further extends EO to dealwith the MOPs. The main research work includes: (1) Based on the analysis on the mechanism of EO, this paper presents a new algorithmnamed population-based EO with adaptive Le′vy mutation (PEO). Compared with threestate-of-the-art stochastic search methods with six benchmark functions, it has beenshown that our approach is a good choice to deal with the numerical constrained opti-mization problems.(2) To overcome the limitation of standard PSO, this paper proposes a novel hybrid algo-rithm, called hybrid PSO-EO algorithm, through introducing EO to PSO. The hybridapproach elegantly combines the exploration ability of PSO with the exploitation abil-ity of EO and thus the hybrid algorithm can help standard PSO to jump out of the localoptima. The proposed approach is validated using six complex unimodal/multimodalbenchmark functions. The simulation results demonstrate that the proposed approachis capable of avoiding premature convergence. Thus, the hybrid PSO-EO algorithmcan be considered a good alternative to solve complex numerical function optimiza-tion problems.(3) Since there is merely mutation operation in EO, the mutation operator plays a keyrole in EO search. In this paper, we present a new mutation method based on mixingGaussian mutation and Cauchy mutation, called hybrid Gaussian-Cauchy mutation.The new mutation operator combines the advantages of coarse-grained search andfine-grained search. Unlike some switching algorithms which have to decide whento switch between different mutations during search, the hybrid GC mutation does notneed to make such decisions.(4) In order to extend EO to solve the MOPs, in this work, we propose a novel multiob-jective optimization algorithm, called Multiobjective Extremal Optimization (MOEO),through introducing the fitness assignment based on Pareto optimality to EO. In thispaper, MOEO has been successfully applied to solving unconstrained or constrainedMOPs. The simulation results indicate that the proposed approach is highly competi-tive with three state-of-the-art multiobjective evolutionary algorithms (MOEAs), i.e.,NSGA-II, SPEA2 and PAES. This paper also successfully extends MOEO to solvethe multiobjective 0/1 knapsack problems. The experimental results demonstrate thatthe proposed approach is highly competitive with three state-of-the-art MOEAs, i.e.,NSGA,SPEA and NPGA.(5) The proposed MOEO algorithm is applied to handling four mechanical component de-sign problems reported in the specialized literature. The experimental results demon- strate that MOEO can find the nondominated solutions with good performance in bothaspects of convergence and diversity. The results also show that MOEO is highlycompetitive with NSGA-II, SPEA2 and PAES. Thus MOEO can be considered a goodalternative to solve engineering MOPs.(6) The MOEO algorithm is applied to solving five benchmark stock portfolio optimiza-tion problems. It is demonstrated that MOEO is highly competitive with NSGA-II andSPEA2, and superior to PAES. As a consequence, MOEO is an effective method fordealing with MOPs in the fields of managements and decision-making.