Font Size: a A A

Heuristic Optimization Algorithms And Their Applications In Several Typical Optimization Problems

Posted on:2016-05-19Degree:DoctorType:Dissertation
Country:ChinaCandidate:X Y KongFull Text:PDF
GTID:1318330542989750Subject:Control theory and control engineering
Abstract/Summary:PDF Full Text Request
Heuristic optimization algorithms and their applications have obtained widespread attention in recent years and they have been applied in many practical fields.Some of them and their applications are studied including differential evolution algorithm,particle swarm optimization algorithm and harmony search algorithm.And the main work is as follows.(1)To overcome some drawbacks of the existing binary HS(harmony search)variants,a simplified binary harmony search(SBHS)algorithm is proposed as an extension of HS for tackling 0-1 knapsack problems efficiently.Firstly,an ingenious improvisation scheme without any parameter is introduced.In contrast to the existing HS variants,it depends on the difference between harmonies in the HM(harmony memory)rather than the parameters PAR(pitch adjustment rate)and bw(step bandwidth).This significantly alleviates the burden of manually finding the suitable values for parameters.Moreover,HMCR(harmony memory considering rate)values are dynamically tuned in accordance with the problem dimensions.This proposed approach enables SBHS to suit various problems with greater optimization capacity.Furthermore,the properties of 0-1 knapsack problems are studied thoroughly and specific heuristic is derived to guide the local search around the infeasible solutions to find better solutions.This repair procedure can ensure the availability of solutions and enhance the accuracy and convergence of SBHS at the same time.Finally,SBHS is evaluated and compared with a large amount of HS variants on low-dimensional and high-dimensional 0-1 knapsack problems.The experimental results show that SBHS is superior to recently published HS variants in terms of search accuracy,convergence speed and robustness.(2)Further study on harmony search is conducted and a new binary harmony search algorithm(NBHS)is proposed for solving large-scale multidimensional knapsack problems more effectively.Different from the classical HS designed for problems in continuous space,the framework of HS in NBHS is adjusted corresponding to the characteristics of discrete problems.The proposed method is different from the classical HS in the following four aspects.Firstly,compared to the float coding method used in classical HS,it is more appropriate for the variables to be coded in binary scheme for binary optimization problems in NBHS.Secondly,the probability distribution of each decision variable is the focus instead of the exact value and the concept of mean harmony is introduced in the memory consideration which takes full advantage of the preferable information in the HM.A dynamic parameter adjustment scheme of HMCR is also presented in the memory consideration,which can dynamically update HMCR to better adapt to the evolution of the search process.Thirdly,an ingenious pitch adjustment scheme is executed in NBHS according to the difference between two randomly selected harmonies stored in the HM to generate a new candidate harmony without any specified parameters including PAR and bw utilized in other HS variants.Finally,a new simple but effective repair operator derived from the specific knowledge of the MKP is introduced to embed in the NBHS algorithm to enhance the exploitation ability and convergence speed.Through the repair operator,it can be guaranteed that all harmonies stored in the HM are feasible.Finally,extensive numerical simulations are conducted on two sets of large-scale benchmark problems,and the results reveal that the proposed method is robust and effective for solving the multidimensional knapsack problems with large dimension sizes.(3)Applications of particle swarm optimization in integer programming are focused and the specific RAP model with multiple strategy choices(RAP-MSC)is chosen as a practical application background.The consideration of redundancy strategies as an additional decision variable for each subsystem makes it more realistic for modeling the systems.However,difficulties arise due to the tremendous search space,especially in large-scale systems.We are motivated to apply meta-heuristic approaches to solve such NP-hard problems in real cases and a simplified particle swarm optimization(SPSO)algorithm is proposed to compensate for the lack of efficient solution techniques to achieve better optimal solutions.This method replaces the velocity updating by a new position updating scheme with a stochastic disturbance.Extensive comparative experiments with PSO variants and other state-of-the-art approaches for RAP-MSC are conducted to evaluate its performance.The results demonstrate that the proposed SPSO algorithm outperforms all comparison methods and is confirmed as a promising alternative for tackling the complicated RAP-MSC.(4)A prediction strategy is proposed according to the Lipschitz condition to handle the constraint and thus a new adaptive grouping differential evolution(AGDE)algorithm is derived to improve the optimization performance for the constrained optimization problems.It is unnecessary to calculate the constraint values when dealing with the constraints in this prediction method.The constraints are handled after a simple prediction according to the Lipschitz condition.When the constraints are very complex,the load arisen from the calculation of the constraint values is reduced dramatically and the feasibility of the solutions remains with great probability.In the AGDE algorithm,the population is dynamically grouped to three subpopulations with respective newly-designed mutation strategy.Meanwhile,the mutation factor and crossover probability are adopted associated with the evolutionary process according to the information of the entire population.Both of the above improvements not only increase the diversity of population and speed up the convergence,but also reduce the complexity of the parameter selection.Four sets of comparative experiments are carried out to evaluate the feasibility and effectiveness of the proposed method that deals with the constraints.
Keywords/Search Tags:Heuristic optimization algorithm, Differential evolution algorithm, Particle swarm optimization, Harmony search algorithm, 0-1 knapsack problem, Multidimensional knapsack problem, System reliability problem, Constrained optimization problem
PDF Full Text Request
Related items