Research on solving optimization problems with neighborhood field

Abstract

Inspired by local cooperation behaviors in the real world, a new evolutionary algorithm - Contour Gradient Optimization algorithm (CGO) - is proposed for solving optimization problems. CGO is a new type of global search algorithm that emulates the cooperative behavior between neighbors. Each individual in CGO evolves in its neighboring environment to find a fit region. The evolving direction is measured by the field generated by nearest individuals. The field includes the attractive force from its better neighbor with higher fitness value and the repulsive force from its worse neighbor with lower fitness value. The simulation results show that CGO is able to solve the multimodal optimization problems globally. The comparative analysis verifies that CGO performs better than some existing algorithms in the respect of accuracy and effectiveness. Based on CGO, we propose an improved algorithm called Neighborhood Field Optimization algorithm that utilizes the cooperation of neighbors directly. NFO utilizes exact neighbors to generate directions of search without need of sorting the population. Using graph theory, we also analyze how the local cooperation phenomenon helps optimization. The proposed NFO is compared with other widely used evolutionary algorithms under different benchmark functions. The presented results show that the cooperation behavior is proven in its significance to model a search method. NFO needs fewer parameters than CGO, but obtains better performance than CGO. Besides the single objective algorithms mentioned above, the neighborhood field model has been successfully extended in multiobjective optimization. A new algorithm called Multiobjective Neighborhood Field Optimization (MONFO) algorithm is able to find the Pareto optima accurately and diversely. In MONFO, the neighborhood field can drive each individual towards its superior neighbor (with higher Pareto rank) and away from the inferior neighbor (with lower Pareto rank). MONFO is compared with other popular multiobjective algorithms under twelve test functions. The results of MONFO are competitive in the respects of accuracy and diversity, especially for multimodal problems. The proximity-based neighborhood field search (NFS) is combined with decomposed Differential Evolution (DE) algorithm to enhance the local exploitation. A new mutation strategy is proposed for differential evolution algorithm (DE). The proposed strategy decomposes the population into several subpopulations with sharing useful information, while most existing decomposed strategies isolate each subpopulation. We find that sharing information could enhance DE to exploit and explore the search space in a more suitable way than not sharing. The proximity-based local search, i.e., NFS, is newly employed in the decomposed subpopulation to accelerate the convergence of DE. We have compared the proposed algorithms with some state-of-the-art algorithms on a comprehensive set of benchmarks. The results show that our algorithms could converge to the global optimum with better performance than others. To solve practical application problems, a new discrete optimization algorithm called binary neighborhood field optimization (BNFO) is proposed based on the neighborhood field model. As a kind of global search algorithm, BNFO is able to deliver promising results efficiently within given computational time. BNFO is applied to solve the unit commitment problem (UCP), whose objective is to minimize the operation cost of the generation units over the scheduling horizon. After numerical tests on several benchmarks, BNFO can converge to promising results with less computation time for these problems.

Date of Award	15 Feb 2013
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Wai Shing Tommy CHOW (Supervisor)