جستجوی آزاد همراه با بهره برداری تکاملی تطبیقی دیفرانسیلی و اکتشاف الهام گرفته از کوانتوم
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|20403||2012||17 صفحه PDF||سفارش دهید||محاسبه نشده|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Journal of Network and Computer Applications, Volume 35, Issue 3, May 2012, Pages 1035–1051
Recently an interesting evolutionary mechanism, sensibility, inherited from a concept model of Free Search (FS) was introduced and used for solving network problems. Unfortunately, the original FS is not easy to implement because it requires key knowledge that is not clearly defined in the existing literature to determine the neighborhood space that profoundly affects the performance of the original FS. This paper thus designs a new implementation for the concept model of FS, and proposes a new algorithm, called Free Search with Adaptive Differential Evolution Exploitation and Quantum-Inspired Exploration (ADEQFS) to address this issue. In ADEQFS, we focus on designing a new mutation strategy by employing adaptive differential evolution techniques as well as concepts and principles from real-coded quantum-inspired evolutionary algorithm. In addition, we use the crossover operation from the traditional Differential Evolution scheme to alleviate the premature convergence for the proposed algorithm. Furthermore, we employ the greedy mechanism to preserve the best solutions found at each generation. The convergence analysis of the proposed algorithm is also presented in this paper. We give the proof of convergence by using the Markov chain model. Thirty-four optimization test functions with different mathematical characteristics are employed as benchmark set to test the performance of ADEQFS. The numerical results highlight the improved convergence rate and computation reliability.
Recently, the evolutionary computation algorithms have drawn a great attention to researchers. They have been introduced to solve problems in computer network (Bernardino et al., 2011, Hanning et al., 2011, Mohammad et al., 2012, Wenjia and Bo, 2011 and Dhurandher et al., 2011). In 2005, Penev and Littlefair (2005) proposed a new population-based evolutionary algorithm—Free Search (FS). Compared with other population-based algorithms, the distinguished feature with regard to the conceptual model is that FS has no restriction of zero probability for the search space, and subsequently it can cope with heterogeneous optimization problems (Penev, 2009). FS can be likened to the heuristic behavior of variety of animals in nature, where they search surrounding environment with the aim of trying to find some favors (Omran and Engelbrecht, 2009). FS has attracted the attention to researchers and has been studied in the literature (Penev and Littlefair, 2005, Penev, 2009, Omran and Engelbrecht, 2009, Guang-Yu et al., 2009 and Wang and Yin, 2011). FS can also be effective in the application of solving engineering problems (Hui et al., 2007 and Ya-ling et al., 2009). Artifacts in the traditional evolutionary algorithms—Genetic Algorithms, Particle Swarm Optimization, Differential Evolution, Ant Colony Optimization, and Artificial Immune System—cannot make free decisions to adjust their behaviors to their environments because these algorithms have previously modeled a system level decision process (Pomerol, 1997, Cass and De Pietro, 1998 and Waltz, 2006). With this concern, FS has developed a mechanism, called sensibility, in which the individuals can make their own decisions based on various senses. An individual level decision process, therefore, is embedded in the concept model of FS, which provides individuals with an ability of artificial thinking. Nevertheless, the original FS is not easy to implement and has its own drawbacks (Omran and Engelbrecht, 2009, Guang-Yu et al., 2009 and Wang and Yin, 2011): The performance of the original FS is affected by the neighborhood space which requires key knowledge that is not clearly defined in existing literature to determine it. In this paper, an effective algorithm, Free Search with Adaptive Differential Evolution Exploitation and Quantum-Inspired Exploration (FS with ADEQ, simply denoted as ADEQFS), is proposed. ADEQFS is easy to implement with rapid convergence speed and high computation reliability. In ADEQFS, we follow the concept model of FS and design a new implement strategy by using concepts and principles borrowed from the adaptive differential evolution (ADE) as well as real-coded quantum-inspired evolutionary algorithm (RQEA). To be specific, the framework of concept model of FS is used to provide the individuals with sensibility in the proposed algorithm. ADE is employed as the exploitation strategy which directs individuals into promising directions more precisely. RQEA, on the other hand, is used as the exploration strategy which drives the individuals towards better solutions at a fast rate. Therefore, the combined two search strategies regarded as mutation operation, if well designed, are capable of improving the performance of proposed algorithm, balancing the search process between exploitation and exploration. Compared with the similar mutation operation in the original FS, the new designed mutation operation is easy to implement, because it does not require defining the neighborhood space. In order to alleviate the premature convergence, the crossover operation, originally from the traditional Differential Evolution, is also introduced in the proposed algorithm. Moreover, we also use the greedy mechanism to preserve the best individuals at each generation. In addition, a theoretical analysis is also presented in this paper by using the Markov chain model to prove the convergence of ADEQFS. Thirty-four test functions are employed as benchmark set to test the performance of the proposed algorithm. These test functions have different mathematical characteristics, which include 14 different scalable functions under conditions of 30 dimensions and 100 dimensions respectively, four low dimensional functions, and two rotated and shifted functions. Simulation results show that in most situations ADEQFS is better than, or in a few cases at least comparable (in terms of convergence performance) to, Enhanced Decision Making Free Search (EDMFS), Multi-Swarm Particle Swarm Optimizer (PS2O), Adaptive Differential Evolution with Optional External Archive (JADE with optional external archive, simply denoted as JADE), and Free Search Differential Evolution (FSDE) from the recent literature. To be specific, ADEQFS achieves the best performance on 23 test functions (f1–f4f1–f4, f6–f7f6–f7, f9–f11f9–f11, and f 13 with both 30 and 100 dimensions; f 14 with 100 dimensions; f 18 and f 20), and obtains comparable results in nine test functions (f 8 and f 12 with both 30 and 100 dimensions; f 14 with 30 dimensions; f15–f17f15–f17 and f19); FSDE gets the best results in five test functions (f5 and f12 with both 30 and 100 dimensions; f8 with 30 dimensions); JADE obtains the best performance on four test functions (f14 with 30 dimensions, f8 with 100 dimensions, f17 and f19); PS2O achieves the best results in one test function (f16); EDMFS obtains the best performance on one test function (f15). The remainder of the paper is organized as follows. In Section 2, key techniques and concepts from FS, ADE, and RQEA are reviewed and discussed. The proposed algorithm, ADEQFS, and its convergence analysis are described in detail in Section 3. Experiments, results interpretation, and analysis are presented in Section 4. Finally, Section 5 gives a concise summary of our work. The following indexes and notations will be adopted in this paper: i The index of vector dimension, i=1,2,…,NDi=1,2,…,ND, where ND is the problem dimension. j The index of individual, j=1,2,…,NPj=1,2,…,NP, where NP is the population size. k The number of selected location with pheromone, k=1,2,…,NPk=1,2,…,NP. g The current iteration, g=1,2,…,Gg=1,2,…,G, where G is the terminate iterative generation. LBi,UBi The greatest lower bound and the greatest upper bound of search space, respectively. rand/rand(0,1)rand/rand(0,1) A random value between 0 and 1.
نتیجه گیری انگلیسی
The recently proposed approach FS has introduced the concept of sensibility which is designed to achieve the aim that the probability for access to any location in the search space is positive. However, this scheme is difficult to implement since it requires a priori key knowledge that is not clearly defined in the existing literature to determine the search neighborhood space. To address this issue, we propose a new implementation strategy for the concept model of Free Search. In the proposed algorithm, i.e., Free Search with Adaptive Differential Evolution Exploitation and Quantum-Inspired Exploration, we focus on designing a new mutation strategy because it is the key component for improving the performance of almost all the evolutionary algorithms. Specifically, in the proposed algorithm, all the individuals, called H-animals, are embedded with two kinds of information, namely adaptive differential evolution information and quantum-inspired information. Then, we design a simple strategy to let H-animals conduct different search processes balanced between the exploitation search and the exploration search. In addition, we employ crossover operation from the traditional DE to alleviate the premature convergence of the proposed algorithm. The crossover operation can be regarded as animals taking steps compared with the concept model of Free Search since these two strategies have the same objective. Furthermore, we also use the greedy mechanism to preserve the best H-animals at each generation. Simulation results have shown significant convergence rate as well as computation reliability improvement for the proposed scheme. In the future work the proposed scheme will be applied to practical applications such as biometrics security (Wang et al., 2007) and the training of the Hidden Markov Model (HMM) based intrusion detection engines (Hoang et al., 2009; Hu et al., 2009).