Baldwinian learning in clonal selection algorithm for optimization

Artificial immune systems are a kind of new computational intelligence methods which draw inspiration from the human immune system. Most immune system inspired optimization algorithms are based on the applications of clonal selection and hypermutation, and known as clonal selection algorithms. These clonal selection algorithms simulate the immune response process based on principles of Darwinian evolution by using various forms of hypermutation as variation operators. The generation of new individuals is a form of the trial and error process. It seems very wasteful not to make use of the Baldwin effect in immune system to direct the genotypic changes. In this paper, based on the Baldwin effect, an improved clonal selection algorithm, Baldwinian Clonal Selection Algorithm, termed as BCSA, is proposed to deal with optimization problems. BCSA evolves and improves antibody population by four operators, clonal proliferation, Baldwinian learning, hypermutation, and clonal selection. It is the first time to introduce the Baldwinian learning into artificial immune systems. The Baldwinian learning operator simulates the learning mechanism in immune system by employing information from within the antibody population to alter the search space. It makes use of the exploration performed by the phenotype to facilitate the evolutionary search for good genotypes. In order to validate the effectiveness of BCSA, eight benchmark functions, six rotated functions, six composition functions and a real-world problem, optimal approximation of linear systems are solved by BCSA, successively. Experimental results indicate that BCSA performs very well in solving most of the test problems and is an effective and robust algorithm for optimization.     

Comparing evolutionary hybrid systems for design and optimization of multilayer perceptron structure along training parameters

In this paper we present a comparative study of several methods that combine evolutionary algorithms and local search to optimize multilayer perceptrons: A method that optimizes the architecture and initial weights of multilayer perceptrons; another that searches for training algorithm parameters, and finally, a co-evolutionary algorithm, introduced here, that handles the architecture, the network’s initial weights and the training algorithm parameters. Our aim is to determine how the co-evolutive method can obtain better results from the point of view of running time and classification ability. Experimental results show that the co-evolutionary method obtains similar or better results than the other approaches, requiring far less training epochs and thus, reducing running time.     

A pareto-based evolutionary algorithm using decomposition and truncation for dynamic multi-objective optimization

Maintaining a balance between convergence and diversity of the population in the objective space has been widely recognized as the main challenge when solving problems with two or more conflicting objectives. This is added by another difficulty of tracking the Pareto optimal solutions set (POS) and/or the Pareto optimal front (POF) in dynamic scenarios. Confronting these two issues, this paper proposes a Pareto-based evolutionary algorithm using decomposition and truncation to address such dynamic multi-objective optimization problems (DMOPs). The proposed algorithm includes three contributions: a novel mating selection strategy, an efficient environmental selection technique and an effective dynamic response mechanism. The mating selection considers the decomposition-based method to select two promising mating parents with good diversity and convergence. The environmental selection presents a modified truncation method to preserve good diversity. The dynamic response mechanism is evoked to produce some solutions with good diversity and convergence whenever an environmental change is detected. In the experimental studies, a range of dynamic multi-objective benchmark problems with different characteristics were carried out to evaluate the performance of the proposed method. The experimental results demonstrate that the method is very competitive in terms of convergence and diversity, as well as in response speed to the changes, when compared with six other state-of-the-art methods.     

应用于高维优化问题的免疫进化算法

针对免疫算法在伞局优化过程中多样性不足的问题,提出一种新型的免疫进化算法.随机克隆扩张和多受体随机编辑算了足该算法的主要特色,同时引入改进的超变异算了加强个体的学习能力;提出一种新的算法件能评价准则,以比较不同算法在全局优化中的表现.实验环节中,首先确定了克降扩张比:然后将免疫进化算法与快速克降算法和Opt-IMMAL...     

A multi-objective evolutionary algorithm for examination timetabling

This paper considers the scheduling of exams for a set of university courses. The solution to this exam timetabling problem involves the optimization of complete timetables such that there are as few occurrences of students having to take exams in consecutive periods as possible but at the same time minimizing the timetable length and satisfying hard constraints such as seating capacity and no overlapping exams. To solve such a multi-objective combinatorial optimization problem, this paper presents a multi-objective evolutionary algorithm that uses a variable-length chromosome representation and incorporates a micro-genetic algorithm and a hill-climber for local exploitation and a goal-based Pareto ranking scheme for assigning the relative strength of solutions. It also imports several features from the research on the graph coloring problem. The proposed algorithm is shown to be a more general exam timetabling problem solver in that it does not require any prior information of the timetable length to be effective. It is also tested against a few influential and recent optimization techniques and is found to be superior on four out of seven publicly available datasets.     

Illustration of fairness in evolutionary multi-objective optimization

It is widely assumed that evolutionary algorithms for multi-objective optimization problems should use certain mechanisms to achieve a good spread over the Pareto front. In this paper, we examine such mechanisms from a theoretical point of view and analyze simple algorithms incorporating the concept of fairness. This mechanism tries to balance the number of offspring of all individuals in the current population. We rigorously analyze the runtime behavior of different fairness mechanisms and present illustrative examples to point out situations, where the right mechanism can speed up the optimization process significantly. We also indicate drawbacks for the use of fairness by presenting instances, where the optimization process is slowed down drastically.     

Joint operations algorithm for large-scale global optimization

Large-scale global optimization (LSGO) is a very important but thorny task in optimization domain, which widely exists in management and engineering problems. In order to strengthen the effectiveness of meta-heuristic algorithms when handling LSGO problems, we propose a novel meta-heuristic algorithm, which is inspired by the joint operations strategy of multiple military units and called joint operations algorithm (JOA). The overall framework of the proposed algorithm involves three main operations: offensive, defensive and regroup operations. In JOA, offensive operations and defensive operations are used to balance the exploration ability and exploitation ability, and regroup operations is applied to alleviate the problem of premature convergence. To evaluate the performance of the proposed algorithm, we compare JOA with six excellent meta-heuristic algorithms on twenty LSGO benchmark functions of IEEE CEC 2010 special session and four real-life problems. The experimental results show that JOA performs steadily, and it has the best overall performance among the seven compared algorithms.     

Convergence analysis of a self-adaptive multi-objective evolutionary algorithm based on grids

Evolutionary algorithms have been successfully applied to various multi-objective optimization problems. However, theoretical studies on multi-objective evolutionary algorithms, especially with self-adaption, are relatively scarce. This paper analyzes the convergence properties of a self-adaptive (μ+1)-algorithm. The convergence of the algorithm is defined, and general convergence conditions are studied. Under these conditions, it is proven that the proposed self-adaptive (μ+1)-algorithm converges in probability or almost surely to the Pareto-optimal front.     

An evolutionary algorithm with directed weights for constrained multi-objective optimization

When solving constrained multi-objective optimization problems (CMOPs), keeping infeasible individuals with good objective values and small constraint violations in the population can improve the performance of the algorithms, since they provide the information about the optimal direction towards Pareto front. By taking the constraint violation as an objective, we propose a novel constraint-handling technique based on directed weights to deal with CMOPs. This paper adopts two types of weights, i.e. feasible and infeasible weights distributing on feasible and infeasible regions respectively, to guide the search to the promising region. To utilize the useful information contained in infeasible individuals, this paper uses infeasible weights to maintain a number of well-diversified infeasible individuals. Meanwhile, they are dynamically changed along with the evolution to prefer infeasible individuals with better objective values and smaller constraint violations. Furthermore, 18 test instances and 2 engineering design problems are used to evaluate the effectiveness of the proposed algorithm. Several numerical experiments indicate that the proposed algorithm outperforms four compared algorithms in terms of finding a set of well-distributed non-domination solutions.     

Algorithmic analysis of a basic evolutionary algorithm for continuous optimization

In practical optimization, applying evolutionary algorithms has nearly become a matter of course. Their theoretical analysis, however, is far behind practice. So far, theorems on the runtime are limited to discrete search spaces; results for continuous search spaces are limited to convergence theory or even rely on validation by experiments, which is unsatisfactory from a theoretical point of view.     

A mathematical framework for passenger screening optimization via a multi-objective evolutionary approach

Concerns regarding the smuggling of dangerous items into commercial flights escalated after the failed Christmas day bomber attack. As a result, the Transportation Security Agency (TSA) has strengthened its efforts to detect passengers carrying hazardous items by installing novel screening technologies and by increasing the number of random pat-downs performed at security checkpoints nationwide. However, the implementation of such measures has raised privacy and health concerns among different groups thus making the design and evaluation of new inspection strategies strongly necessary. This research presents a mathematical framework to design passenger inspection strategies that include the utilization of novel and traditional technologies (i.e. body scanners, explosive detection systems, explosive trace detectors, walk-through metal detectors, and wands) offered by multiple manufacturers, to identify three types of items: metallic, bulk explosives (i.e. plastic, liquids, gels), and traces of explosives. A multiple objective optimization model is proposed to optimize inspection security, inspection cost, and processing time; an evolutionary approach is used to solve the model. The result is a Pareto set of quasi-optimal solutions representing multiple inspection strategies. Each strategy is different in terms of: (1) configuration, (2) the screening technologies included, (3) threshold calibration, and consequently, (4) inspection security, inspection cost, and processing time.     

Nonlinear channel equalizer design using directional evolutionary multi-objective optimization

In this paper, a new equalizer learning scheme is introduced based on the algorithm of the directional evolutionary multi-objective optimization (EMOO). Whilst nonlinear channel equalizers such as the radial basis function (RBF) equalizers have been widely studied to combat the linear and nonlinear distortions in the modern communication systems, most of them do not take into account the equalizers’ generalization capabilities. In this paper, equalizers are designed aiming at improving their generalization capabilities. It is proposed that this objective can be achieved by treating the equalizer design problem as a multi-objective optimization (MOO) problem, with each objective based on one of several training sets, followed by deriving equalizers with good capabilities of recovering the signals for all the training sets. Conventional EMOO which is widely applied in the MOO problems suffers from disadvantages such as slow convergence speed. Directional EMOO improves the computational efficiency of the conventional EMOO by explicitly making use of the directional information. The new equalizer learning scheme based on the directional EMOO is applied to the RBF equalizer design. Computer simulation demonstrates that the new scheme can be used to derive RBF equalizers with good generalization capabilities, i.e., good performance on predicting the unseen samples.     

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows

The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.     

多种群联合的多目标进化自适应阈值图像分割算法*

多阈值图像分割算法的阈值数目大多需要用户指定,人为干预较大。本文提出多种群联合的多目标进化自适应阈值图像分割算法,本文提出多种群联合的多目标进化自适应阈值图像分割算法,在多个分组种群的联合进化框架下,通过同时优化类间方差准则和模糊熵准则获得图像阈值,并在进化过程中采用自调节的交叉和变异操作产生子代种群并自动确定阈值数目。实验结果表明,该算法不仅能自适应得到合适的阈值数目,而且阈值分割效果也是比较理想的。     

Immunity-based hybrid learning methods for approximator structure and parameter adjustment

From the point of view of information processing the immune system is a highly parallel and distributed intelligent system which has learning, memory, and associative retrieval capabilities. In this paper we present two immunity-based hybrid learning approaches for function approximation (or regression) problems that involve adjusting the structure and parameters of spatially localized models (e.g., radial basis function networks). The number and centers of the receptive fields for local models are specified by immunity-based structure adaptation algorithms, while the parameters of the local models, which enter in a linear fashion, are tuned separately using a least-squares method. The effectiveness of the procedure is demonstrated through a nonlinear function approximation problem and a nonlinear dynamical system modeling problem.     

Incorporation of implicit decision-maker preferences in multi-objective evolutionary optimization using a multi-criteria classification method

Nowadays, most Multi-Objective Evolutionary Algorithms (MOEA) concentrate mainly on searching for an approximation of the Pareto frontier to solve a multi-objective optimization problem. However, finding this set does not completely solve the problem. The decision-maker (DM) still has to choose the best compromise solution from that set. But as the number of criteria increases, several important difficulties arise in performing this task. Identifying the Region of Interest (ROI), according to the DM’s preferences, is a promising alternative that would facilitate the selection process. This paper approaches the incorporation of preferences into a MOEA in order to characterize the ROI by a multi-criteria classification method. This approach is called Hybrid Multi-Criteria Sorting Genetic Algorithm and is composed of two phases. First, a metaheuristic is used to generate a small set of solutions that are classified in ordered categories by the DM. Thus, the DM’s preferences will be reflected indirectly in this set. In the second phase, a multi-criteria sorting method is combined with an evolutionary algorithm. The first one is used to classify new solutions. Those classified as ‘satisfactory’ are used for creating a selective pressure towards the ROI. The effectiveness of our method was proved in nine instances of a public project portfolio problem. The obtained results indicate that our approach achieves a good characterization of the ROI, and outperforms the standard NSGA-II in simple and complex problems. Also, these results confirm that our approach is able to deal with many-objective problems.     

Optimal foraging algorithm for global optimization

An optimization algorithm, inspired by the animal Behavioral Ecology Theory—Optimal Foraging Theory, named the Optimal Foraging Algorithm (OFA) has been developed. As a new stochastic search algorithm, OFA is used to solve the global optimization problems following the animal foraging behavior. During foraging, animals know how to find the best pitch with abundant prey; in establishing OFA, the basic operator of OFA was constructed following this foraging strategy. During foraging, an individual of the foraging swarms obtained more opportunities to capture prey through recruitment; in OFA the recruitment was adopted to ensure the algorithm has a higher chance to receive the optimal solution. Meanwhile, the precise model of prey choices proposed by Krebs et al. was modified and adopted to establish the optimal solution choosing strategy of OFA. The OFA was tested on the benchmark functions that present difficulties common to many global optimization problems. The performance comparisons among the OFA, real coded genetic algorithms (RCGAs), Differential Evolution (DE), Particle Swarm Optimization (PSO) algorithm, Bees Algorithm (BA), Bacteria Foraging Optimization Algorithm (BFOA) and Shuffled Frog-leaping Algorithm (SFLA) are carried out through experiments. The parameter of OFA and the dimensions of the multi-functions are researched. The results obtained by experiments and Kruskal-Wallis test indicate that the performance of OFA is better than the other six algorithms in terms of the ability to converge to the optimal or the near-optimal solutions, and the performance of OFA is the second-best one from the view of the statistical analysis.     

Dynamic multi-objective evolutionary algorithms for single-objective optimization

This paper proposes a new method for handling the difficulty of multi-modality for the single-objective optimization problem (SOP). The method converts a SOP to an equivalent dynamic multi-objective optimization problem (DMOP). A new dynamic multi-objective evolutionary algorithm (DMOEA) is implemented to solve the DMOP. The DMOP has two objectives: the original objective and a niche-count objective. The second objective aims to maintain the population diversity for handling the multi-modality difficulty during the search process. Experimental results show that the performance of the proposed algorithm is significantly better than the state-of-the-art competitors on a set of benchmark problems and real world antenna array problems.     

一种求解多目标优化问题的进化算法混合框架

为了提高多目标优化算法的求解性能,提出一种启发式的基于种群的全局搜索与局部搜索相结合的多目标进化算法混合框架.该框架采用模块化、系统化的设计思想,不同模块可以采用不同策略构成不同的算法.采用经典的改进非支配排序遗传算法(NSGA-II)和基于分解的多目标进化算法(MOEA/D)作为进化算法的模块算法来验证所提混合框架的有效性.数值实验表明,所提混合框架具有良好性能,可以兼顾算法求解的多样性和收敛性,有效提升现有多目标进化算法的求解性能.     

A self-adaptive linear evolutionary algorithm for solving constrained optimization problems

In many real-world applications of evolutionary algorithms, the fitness of an individual requires a quantitative measure. This paper proposes a self-adaptive linear evolutionary algorithm (ALEA) in which we introduce a novel strategy for evaluating individual’s relative strengths and weaknesses. Based on this strategy, searching space of constrained optimization problems with high dimensions for design variables is compressed into two-dimensional performance space in which it is possible to quickly identify ‘good’ individuals of the performance for a multiobjective optimization application, regardless of original space complexity. This is considered as our main contribution. In addition, the proposed new evolutionary algorithm combines two basic operators with modification in reproduction phase, namely, crossover and mutation. Simulation results over a comprehensive set of benchmark functions show that the proposed strategy is feasible and effective, and provides good performance in terms of uniformity and diversity of solutions.