افزایش تکامل دیفرانسیل توزیع شده با مهاجرت چند فرهنگی برای بهینه سازی عددی جهانی

Differential evolution (DE) is a prominent stochastic optimization technique for global optimization. After its original definition in 1995, DE frameworks have been widely researched by computer scientists and practitioners. It is acknowledged that structuring a population is an efficient way to enhance the algorithmic performance of the original, single population (panmictic) DE. However, only a limited amount of work focused on Distributed DE (DDE) due to the difficulty of designing an appropriate migration strategy. Since a proper migration strategy has a major impact on the performance, there is a large margin of improvement for the DDE performance. In this paper, an enhanced DDE algorithm is proposed for global numerical optimization. The proposed algorithm, namely DDE with Multicultural Migration (DDEM) makes use of two migration selection approaches to maintain a high diversity in the subpopulations, Target Individual Based Migration Selection (TIBMS) and Representative Individual Based Migration Selection (RIBMS), respectively. In addition, the diversity amongst the individuals is controlled by means of the proposed Affinity Based Replacement Strategy (ABRS) mechanism. Numerical experiments have been performed on 34 diverse test problems. The comparisons have been made against DDE algorithms using classical migration strategies and three popular DDE variants. Experimental results show that DDEM displays a better or equal performance with respect to its competitors in terms of the quality of solutions, convergence, and statistical tests.

Differential evolution (DE), originally proposed by Storn and Price in 1995 [38] and [39], is a popular meta-heuristic for handling continuous optimization problems. In some contexts DE is considered as an Evolutionary Algorithm (EA) because of the mutation and crossover operations and in some other contexts is regarded as a Swarm Intelligence Algorithm (SIA) because of the one-to-one spawning in the survivor selection [26]. Due to its distinguished characteristics, such as few control parameters, simple and straightforward implementation, remarkable performance and low complexity [11], DE has been extensively researched [33], [63] and [20]. It is widely acknowledged that the a proper degree of population diversity is a key factor in the success of both EAs and SIAs, see [8], [28], [44], [27] and [25]. The loss of population diversity may result into premature convergence while an excessive diversity may cause stagnation. The emphasis on population diversity leads to a research direction of designing algorithms using structured population, where the population size varies with the evolution process [43] and [61] or the population is divided into many groups. In this paper, we only consider the later case. According to the size of the groups, structured population can be classified into two categories [2] and [45]: cellular structure and distributed structure. In cellular structure, the population is made up of many tightly connected subpopulations usually composed of only one individual. Each individual has its own neighborhood and is allowed to recombine with only neighboring individuals to produce offspring. In distributed structure, the population is partitioned into several subpopulations and each one independently evolves. At a specific moment, migration is performed to exchange information between subpopulations for enhancing the diversity of subpopulations. Therefore, the migration strategy is an important factor on the performance of the algorithm using distributed population structure. Normally, migration strategy can be characterized by migration interval, migration size, migration topology, migrant selection and replacement selection. In this paper, we will discuss migrant and replacement selection approaches. There are many migrant and replacement selection methods reported in the literature. Most of them are instances or variants of the schemes that the best or random individual in the emigrated subpopulation replaces the worst or random individual in the immigrated subpopulation [55] and [57]. Besides, Cantú-Paz [7] studied the combinations of migration strategies based on random or fitness in a distributed Genetic Algorithm (GA). Noda et al. [29] proposed an adaptive policy for choosing migrants and/or replacements according to some knowledge-oriented rules. In [4], the authors presented the selection of the migrant “relatively” different from the received subpopulation and the migration strategy was integrated with a canonical GA [19]. Compared with distributed GAs and the DE algorithms that use adaptation or self-adaptation mechanisms, less attention was paid to Distributed DE (DDE) because the migration strategy must be carefully designed. Appropriately increasing the diversity is beneficial and enhances the performance, however, excessively increasing the diversity is detrimental as it might quickly cause a stagnation of evolution. This fact is important and must be taken into account when designing a migration strategy for a DDE. Motivated by the principle not too similar, not too different in [4], we propose an enhanced DDE algorithm with Multicultural Migration (DDEM) for global numerical optimization problems. In DDEM, an Affinity Based Replacement Strategy (ABRS) and two types of migrant selection approaches based on Target and Representative Individuals, respectively, are here introduced to effectively improve the population diversities of subpopulations. Specifically, a migrant from a group of elite individuals in the emigrated subpopulation is selected according to its difference from the representative or target individual in the immigrated subpopulation; the replaced individual in the immigrated subpopulation is decided by the affinities between individuals. Thirty-four benchmark functions with various characteristics are chosen from the literature to carry out a large number of experiments. Some DDE algorithms with classical migration strategies and three well-known DDE variants, are used as benchmark algorithms to verify the advantage of DDEM, in terms of the quality of solutions, convergence, and statistical tests. The remainder of this paper is organized as follows. Section 2 describes the canonical DE algorithm. In Section 3, an overview of related work is presented. Then the proposed DDEM algorithm is described in Section 4. Extensive experiments are provided in Section 5. Section 6 concludes this paper.

This paper investigates DDE schemes and their migration strategies as they have a major impact on the performance of the algorithm. By taking into account the consideration that the migrant should not be too similar and not too different from the immigrated subpopulation, a DDE algorithm with a multicultural migration strategy is here proposed. The proposed algorithm combines two newly proposed migration schemes and with a novel selection mechanism based on the affinity of the individuals. Numerical results show that DDEM produces better performance than other DDE algorithms with classical migration strategies and three well-known DDE variants in terms of several different performance metrics. Possible directions in future work may exploit two aspects. The first is that the dynamics of population structure and adaptation or self-adaptation parameters, such as migration interval, scale factor or crossover rate, can be used to further improve the DDEM performance. Another interesting topic is the introduction of the multicultural migration strategy into other distributed EAs or distributed SIAs since it is generic and independent of the used meta-heuristic.