A multiagent genetic algorithm for global numerical optimization.

In this paper, multiagent systems and genetic algorithms are integrated to form a new algorithm, multiagent genetic algorithm (MAGA), for solving the global numerical optimization problem. An agent in MAGA represents a candidate solution to the optimization problem in hand. All agents live in a latticelike environment, with each agent fixed on a lattice-point. In order to increase energies, they compete or cooperate with their neighbors, and they can also use knowledge. Making use of these agent-agent interactions, MAGA realizes the purpose of minimizing the objective function value. Theoretical analyzes show that MAGA converges to the global optimum. In the first part of the experiments, ten benchmark functions are used to test the performance of MAGA, and the scalability of MAGA along the problem dimension is studied with great care. The results show that MAGA achieves a good performance when the dimensions are increased from 20-10,000. Moreover, even when the dimensions are increased to as high as 10,000, MAGA still can find high quality solutions at a low computational cost. Therefore, MAGA has good scalability and is a competent algorithm for solving high dimensional optimization problems. To the best of our knowledge, no researchers have ever optimized the functions with 10,000 dimensions by means of evolution. In the second part of the experiments, MAGA is applied to a practical case, the approximation of linear systems, with a satisfactory result.     

改进的多智能体遗传算法求解TSP研究

多智能体遗传算法是基于智能体对环境感知与反作用的能力提出的一种新的函数优化方法,具有很快的收敛速度,尤其是在优化超高维函数时更显示出了它的优越性。针对这一特点对该算法进行了适当的改进,在邻域正交交叉算子中采用精英保留策略,在自学习算子中引入邻域正交交叉算子并采用小变异概率以加快收敛速度。求解TSP的实验结果显示,改进后算法的性能有了较大的提高。     

Tabu search with multi-level neighborhood structures for high dimensional problems

Metaheuristics have been successfully applied to solve different types of numerical and combinatorial optimization problems. However, they often lose their effectiveness and advantages when applied to large and complex problems. Moreover, the contributions of metaheuristics that deal with high dimensional problems are still very limited compared with low and middle dimensional problems. In this paper, Tabu Search algorithm based on variable partitioning is proposed for solving high dimensional problems. Specifically, multi-level neighborhood structures are constructed by partitioning the variables into small groups. Some of these groups are selected and the neighborhood of their variables are explored. The computational results shown later indicate that exploring the neighborhood of all variables at the same time, even for structured neighborhood, can badly effect the progress of the search. However, exploring the neighborhood gradually through smaller number of variables can give better results. The variable partitioning mechanism used in the proposed method can allow the search process to explore the region around the current iterate solution more precisely. Actually, this partitioning mechanism works as dimensional reduction mechanism. For high dimensional problems, extensive computational studies are carried out to evaluate the performance of newly proposed algorithm on large number of benchmark functions. The results show that the proposed method is promising and produces high quality solutions within low computational costs.     

多智能体遗传算法用于线性系统逼近

提出了一种新的参数优化方法--多智能体遗传算法,来求解线性系统逼近问题. 该方法中每个智能体代表一个候选解,即搜索空间中的一个实值向量.所有智能体生存在一 个网格状的环境中,且每个智能体占据一个格点不能移动.为了增加能量,它们将与其邻域 进行合作或竞争,也可以利用自身的知识.因此,设计了4个进化算子来模拟智能体间的竞 争、合作、自学习等行为.该方法利用这些智能体与智能体间的相互作用来达到优化逼近模 型中参数的目的;此外,还采用了一种动态扩展搜索空间的方法以解决算法所需的搜索空间 难以确定的问题.实验中,利用一个稳定和一个非稳定的线性系统逼近问题来验证算法的性 能,并与两种新近提出的方法作了比较.结果表明,该文方法优于其它方法,能够用较少的计 算量找到高质量的逼近模型,具有良好的性能和实际应用价值.     

Multi-population co-genetic algorithm with double chain-like agents structure for parallel global numerical optimization

For the low optimization precision and long optimization time of genetic algorithm, this paper proposed a multi-population agent co-genetic algorithm with chain-like agent structure (MPAGA). This algorithm adopted multi-population parallel searching mode, close chain-like agent structure, cycle chain-like agent structure, dynamic neighborhood competition and orthogonal crossover strategy to realize parallel optimization, and has the characteristics of high optimization precision and short optimization time. In order to verify the optimization precision of this algorithm, some popular benchmark test functions were used for comparing this algorithm and a popular agent genetic algorithm (MAGA). The experimental results show that MPAGA has higher optimization precision and shorter optimization time than MAGA.     

基于差异化邻域策略的分解多目标进化算法*

子问题邻域对基于分解的多目标进化算法性能影响较大.当邻域过大时,种群繁殖产生的新解偏离Pareto解集,在更新子问题时,新解与邻域内旧解的比较次数增多,算法的计算复杂度增加;当邻域过小时,算法容易陷入局部最优.为了解决上述问题,文中提出基于差异化邻域策略的分解多目标进化算法(MOEA/D-DN),通过分析不同大小的邻域对算法性能的影响,选择合适的参数.并根据每个子问题的权重向量与中心向量的偏角,为各子问题设置不同大小的邻域,合理分配算法资源,提高算法搜索全局最优解的速率.在2维ZDT系列和3维、5维DTLZ系列测试函数上的实验表明,MOEA/D-DN 的收敛速度与收敛性能均有明显提高,算法的计算资源分配更合理,所获解集整体质量更优.     

Performance Evaluation of Multiagent Genetic Algorithm

Zhong et al. (2004 [IEEE Trans. on Systems, Man and Cybernetics (Part B), 34: 1128–1141]) proposed the multiagent genetic algorithm (MAGA) in their publication titled “A multiagent genetic algorithm for global numerical optimization”. The MAGA exploits the known characteristics of some benchmark functions to achieve outstanding results. For example, the MAGA exploits the fact that all variables have the same numerical value at the global optimum and the same upper and lower bounds to solve several 100 dimensional and 1000 dimensional benchmark problems with high precision requiring on average 7000 and 16,000 function evaluations respectively. In this paper, we evaluate the performance of the MAGA experimentally¹ and demonstrate that the performance of the MAGA significantly deteriorates when the relative positions of the variables at the global optimal point are shifted with respect to the search ranges.     

Two coding based adaptive parallel co-genetic algorithm with double agents structure

This paper systematically proposed a multi-population agent co-genetic algorithm with double chain-like agent structure (MPATCGA) to solve the problem of the low optimization precision and long optimization time of simple genetic algorithm in terms of two coding strategy. This algorithm adopted multi-population parallel searching mode, close chain-like agent structure, cycle chain-like agent structure, dynamic neighborhood competition, and improved crossover strategy to realize parallel optimization, and has the characteristics of high optimization precision and short optimization time. Besides, the size of each sub-population is adaptive. The characteristic is very competitive when dealing with imbalanced workload. In order to verify the optimization precision of this algorithm with binary coding, some popular benchmark test functions were used for comparing this algorithm and a popular agent genetic algorithm (MAGA). The experimental results show that MPATCGA has higher optimization precision and shorter optimization time than MAGA. Besides, in order to show the optimization performance of MPATCGA with real coding, the authors used it for feature selection problems as optimization algorithm and compared it with some other well-known GAs. The experimental results show that MPATCGA has higher optimization precision (feature selection precision). In order to show the performance of the adaptability of size of sub-populations, MPATCGA with sub-populations with same size and MPATCGA with sub-populations with different size are compared. The experimental results show that when the workload on different sub-populations becomes not same, the adaptability will adaptively change the size of different sub-population to obtain precision as high as possible.     

Handling expensive multi-objective optimization problems with a cluster-based neighborhood regression model

This paper gives attention to multi-objective optimization in scenarios where objective function evaluation is expensive, that is, expensive multi-objective optimization. We firstly propose a cluster-based neighborhood regression model, which incorporates the linear regression technique to predict the descent direction and generate new potential offspring. Combining this model with the classical decomposition-based multi-objective optimization framework, we propose an efficient and effective algorithm for tackling computationally expensive multi-objective optimization problems. As opposed to the conventional approach of replacing the original time-consuming objective functions with the approximated ones obtained by surrogate model, the proposed algorithm incorporates the proposed regression model to serve as an operator producing higher-quality offspring so that the algorithm requires fewer iterations to reach a given solution quality. The proposed algorithm is compared with several state-of-the-art surrogate-assisted algorithms on a variety of well-known benchmark problems. Empirical results demonstrate that the proposed algorithm outperforms or is competitive with other peer algorithms, and has the ability to keep a good trade-off between solution quality and running time within a fairly small number of function evaluations. In particular, our proposed algorithm shows obvious superiority in terms of the computational time used for the algorithm components, and can obtain acceptable solutions for expensive problems with high efficiency.     

An improved multi-agent genetic algorithm for numerical optimization

Multi-agent genetic algorithm (MAGA) is a good algorithm for global numerical optimization. It exploited the known characteristics of some benchmark functions to achieve outstanding results. But for some novel composition functions, the performance of the MAGA significantly deteriorates when the relative positions of the variables at the global optimal point are shifted with respect to the search ranges. To this question, an improved multi-agent genetic algorithm for numerical optimization (IMAGA) is proposed. IMAGA make use of the agent evolutionary framework, and constructs heuristic search and a hybrid crossover strategy to complete the competition and cooperation of agents, a convex mutation operator and some local search to achieve the self-learning characteristic. Using the theorem of Markov chain, the improved multi-agent genetic algorithm is proved to be convergent. Experiments are conducted on some benchmark functions and composition functions. The results demonstrate good performance of the IMAGA in solving complicated composition functions compared with some existing algorithms.     

The hyperspherical acceleration effect particle swarm optimizer

This paper proposes Hyperspherical Acceleration Effect Particle Swarm Optimization (HAEPSO) for optimizing complex, multi-modal functions. The HAEPSO algorithm finds the particles that are trapped in deep local minima and accelerates them in the direction of global optima. This novel technique improves the efficiency by manipulating PSO parameters in hyperspherical coordinate system. Performance comparisons of HAEPSO are provided against different PSO variants on standard benchmark functions. Results indicate that the proposed algorithm gives robust results with good quality solution and faster convergence. The proposed algorithm is an effective technique for solving complex, higher dimensional multi-modal functions.     

H.264帧内预测模式快速选择算法

为降低帧内预测的复杂度,提出一种快速的帧内预测算法。该算法利用帧内4×4块最优预测模式与和它相邻的预测模式之间率失真代价（RDCost）的高相关性,以及绝对变换误差和（SATD）与率失真（RD）性能之间的强相关性,有效减少了预测模式,避免了不必要的RDCost计算。实验结果显示,该算法提高编码时间效率约为50%,同时保持视频的图像质量几乎不变。     

改进和声搜索算法及其在连续函数优化中的应用

针对一般和声搜索(HS)算法在求解连续函数优化问题时存在的困难,提出一种改进的多样化和声搜索(IDHS)算法。该算法借鉴模拟退火算法的思想对参数的更新方式作出调整,并且限制保存在和声记忆矩阵中的一致和声的数量以增加解的多样性。数值仿真结果表明,与其他几种传统的和声搜索算法相比,该方法进一步提高了计算精度和收敛速度,以及全局寻优能力。     

Complete neighborhood preserving embedding for face recognition

Neighborhood preserving embedding (NPE) is a linear approximation to the locally linear embedding algorithm which can preserve the local neighborhood structure on the data manifold. However, in typical face recognition where the number of data samples is smaller than the dimension of data space, it is difficult to directly apply NPE to high dimensional matrices because of computational complexity. Moreover, in such case, NPE often suffers from the singularity problem of eigenmatrix, which makes the direct implementation of the NPE algorithm almost impossible. In practice, principal component analysis or singular value decomposition is applied as a preprocessing step to attack these problems. Nevertheless, this strategy may discard dimensions that contain important discriminative information and the eigensystem computation of NPE could be unstable. Towards a practical dimensionality reduction method for face data, we develop a new scheme in this paper, namely, the complete neighborhood preserving embedding (CNPE). CNPE transforms the singular generalized eigensystem computation of NPE into two eigenvalue decomposition problems. Moreover, a feasible and effective procedure is proposed to alleviate the computational burden of high dimensional matrix for typical face image data. Experimental results on the ORL face database and the Yale face database show that the proposed CNPE algorithm achieves better performance than other feature extraction methods, such as Eigenfaces, Fisherfaces and NPE, etc.     

Local search versus Path Relinking in metaheuristics: Redesigning Meta-RaPS with application to the multidimensional knapsack problem

Most heuristics for discrete optimization problems consist of two phases: a greedy-based construction phase followed by an improvement (local search) phase. Although the best solutions are usually generated after the improvement phase, there is usually a high computational cost for employing a local search algorithm. This paper seeks another alternative to reduce the computational burden of a local search while keeping solution quality by embedding intelligence in metaheuristics. A modified version of Path Relinking is introduced to replace the local search in the improvement phase of Meta-RaPS (Meta-Heuristic for Randomized Priority Search) which is currently classified as a memoryless metaheuristic. The new algorithm is tested using the 0–1 multidimensional knapsack problem, and it is observed that it could solve even the largest benchmark problems in significantly less time while maintaining solution quality compared to other algorithms in the literature.     

Two-phase neighborhood search algorithm for two-agent hybrid flow shop scheduling problem

In this paper hybrid flow shop scheduling problem with two agents is studied and its feasibility model is considered. A two-phase neighborhood search (TNS) algorithm is proposed to minimize objectives of two agents simultaneously under the given upper bounds. TNS is constructed through the combination of multiple variable neighborhood mechanisms and a new perturbation strategy for new current solution. A new replacement principle is also applied to decide if the current solution can be updated. TNS is tested on a number of instances and compared with the existing methods. The computational results show the promising advantage of TNS on the considered problem.     

An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems

This paper proposes an effective hybrid tabu search algorithm (HTSA) to solve the flexible job-shop scheduling problem. Three minimization objectives – the maximum completion time (makespan), the total workload of machines and the workload of the critical machine are considered simultaneously. In this study, a tabu search (TS) algorithm with an effective neighborhood structure combining two adaptive rules is developed, which constructs improved local search in the machine assignment module. Then, a well-designed left-shift decoding function is defined to transform a solution to an active schedule. In addition, a variable neighborhood search (VNS) algorithm integrating three insert and swap neighborhood structures based on public critical block theory is presented to perform local search in the operation scheduling component. The proposed HTSA is tested on sets of the well-known benchmark instances. The statistical analysis of performance comparisons shows that the proposed HTSA is superior to four existing algorithms including the AL + CGA algorithm by Kacem, Hammadi, and Borne (2002b), the PSO + SA algorithm by Xia and Wu (2005), the PSO + TS algorithm by Zhang, Shao, Li, and Gao (2009), and the Xing’s algorithm by Xing, Chen, and Yang (2009a) in terms of both solution quality and efficiency.     

Weighted Superposition Attraction (WSA): A swarm intelligence algorithm for optimization problems – Part 1: Unconstrained optimization

This paper is the first one of the two papers entitled “Weighted Superposition Attraction (WSA)”, which is based on two basic mechanisms, “superposition” and “attracted movement of agents”, that are observable in many systems. Dividing this paper into two parts raised as a necessity because of their individually comprehensive contents. If we wanted to write these papers as a single paper we had to write more compact as distinct from its current versions because of the space requirements. So, writing them as a single paper would not be as effective as we desired.In many natural phenomena it is possible to compute superposition or weighted superposition of active fields like light sources, electric fields, sound sources, heat sources, etc.; the same may also be possible for social systems as well. An agent (particle, human, electron, etc.) may be supposed to move towards superposition if it is attractive to it. As systems status changes the superposition also changes; so it needs to be recomputed. This is the main idea behind the WSA algorithm, which mainly attempts to realize this superposition principle in combination with the attracted movement of agents as a search procedure for solving optimization problems in an effective manner. In this current part, the performance of the proposed WSA algorithm is tested on the well-known unconstrained continuous optimization functions, through a set of computational study. The comparison with some other search algorithms is performed in terms of solution quality and computational time. The experimental results clearly indicate the effectiveness of the WSA algorithm.     

链式多种群多智能体进化算法

将多种群的进化方式和链式结构的动态邻域引入到多智能体进化算法中,提出了一种链式多种群多智能体进化算法.算法设置了多种群交互的演化结构.各种群中的智能体通过与其动态邻域智能体的竞争、合作及自学习操作来增加自身的能量;动态邻域的链式结构提高了算法的效率、降低了计算复杂度;多个种群之间的信息定期以一定的方式进行交互,增强了种群的多样性,减小了算法陷入局部最优的机率.理论分析和多个测试函数的仿真结果均表明:链式多种群多智能体进化算法在求解高维优化问题上具有很好的性能.     

Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion

Recently, iterated greedy algorithms have been successfully applied to solve a variety of combinatorial optimization problems. This paper presents iterated greedy algorithms for solving the blocking flowshop scheduling problem (BFSP) with the makespan criterion. Main contributions of this paper can be summed up as follows. We propose a constructive heuristic to generate an initial solution. The constructive heuristic generates better results than those currently in the literature. We employ and adopt well-known speed-up methods from the literature for both insertion and swap neighborhood structures. In addition, an iteration jumping probability is proposed to change the neighborhood structure from insertion neighborhood to swap neighborhood. Generally speaking, the insertion neighborhood is much more effective than the swap neighborhood for the permutation flowshop scheduling problems. Instead of considering the use of these neighborhood structures in a framework of the variable neighborhood search algorithm, two powerful local search algorithms are designed in such a way that the search process is guided by an iteration jumping probability determining which neighborhood structure will be employed. By doing so, it is shown that some additional enhancements can be achieved by employing the swap neighborhood structure with a speed-up method without jeopardizing the effectiveness of the insertion neighborhood. We also show that the performance of the iterated greedy algorithm significantly depends on the speed-up method employed. The parameters of the proposed iterated greedy algorithms are tuned through a design of experiments on randomly generated benchmark instances. Extensive computational results on Taillard’s well-known benchmark suite show that the iterated greedy algorithms with speed-up methods are equivalent or superior to the best performing algorithms from the literature. Ultimately, 85 out of 120 problem instances are further improved with substantial margins.