بهره برداری فشرده تحول دیفرانسیلی برای مسائل بهینه سازی حافظه محدود مختل

This paper proposes a novel and unconventional Memetic Computing approach for solving continuous optimization problems characterized by memory limitations. The proposed algorithm, unlike employing an explorative evolutionary framework and a set of local search algorithms, employs multiple exploitative search within the main framework and performs a multiple step global search by means of a randomized perturbation of the virtual population corresponding to a periodical randomization of the search for the exploitative operators. The proposed Memetic Computing approach is based on a populationless (compact) evolutionary framework which, instead of processing a population of solutions, handles its statistical model. This evolutionary framework is based on a Differential Evolution which cooperatively employs two exploitative search operators: the first is based on a standard Differential Evolution mutation and exponential crossover, and the second is the trigonometric mutation. These two search operators have an exploitative action on the algorithmic framework and thus contribute to the rapid convergence of the virtual population towards promising candidate solutions. The action of these search operators is counterbalanced by a periodical stochastic perturbation of the virtual population, which has the role of “disturbing” the excessively exploitative action of the framework and thus inhibits its premature convergence. The proposed algorithm, namely Disturbed Exploitation compact Differential Evolution, is a simple and memory-wise cheap structure that makes use of the Memetic Computing paradigm in order to solve complex optimization problems. The proposed approach has been tested on a set of various test problems and compared with state-of-the-art compact algorithms and with some modern population based meta-heuristics. Numerical results show that Disturbed Exploitation compact Differential Evolution significantly outperforms all the other compact algorithms present in literature and reaches a competitive performance with respect to modern population algorithms, including some memetic approaches and complex modern Differential Evolution based algorithms. In order to show the potential of the proposed approach in real-world applications, Disturbed Exploitation compact Differential Evolution has been implemented for performing the control of a space robot by simulating the implementation within the robot micro-controller. Numerical results show the superiority of the proposed algorithm with respect to other modern compact algorithms present in literature.

Memetic Computing (MC) is a promising and broad research area in computer science which considers the meme as the unit of information with the purpose of solving problems, see [56] and [57]. The concept of meme is borrowed from philosophy and is intended as the unit of cultural transmission. In other words, complex ideas can be decomposed into memes which propagate and mutate within a population. Culture, in this way, constantly undergoes evolution and tends towards progressive improvements. In computer science, the concept of meme can be identified as a search strategy, an agent, or an operator belonging to a complex system, e.g. an optimization algorithm, which is evolving over time. The earliest example of the MC paradigm is the Memetic Algorithm (MA) [47], i.e. a hybrid evolutionary algorithm which employs deterministic local search within the evolutionary cycle in order to solve a given optimization problem. The importance and need of MC in optimization must be put into relationship with the No Free Lunch Theorem (NFLT) [77], which mathematically proves that the average performance of any pair of algorithms A and B across all possible problems is identical. Thus, if an algorithm performs well on a certain class of problems, then it necessarily pays for that with degraded performance on the set of all remaining problems, as this is the only way that all algorithms can have the same performance averaged over all functions. Strictly speaking, the proof of NFLT is made under the hypothesis that both the algorithms A and B are non-revisiting, i.e. the algorithms do not perform the fitness evaluation of the same candidate solution more often than once during the optimization run. Although this hypothesis is de facto not respected for most of the computational intelligence optimization algorithms, the concept that there is no universal optimizer had a significant impact on the scientific community. It must be observed that until the NFLT publication, Evolutionary Algorithms (EAs) were extremely popular among computer scientists, and their related research was oriented towards the design of algorithms having a superior performance with respect to all the other algorithms present in literature. This approach is visible in many famous texts published in those years, e.g. [21]. After the NFLT diffusion, researchers in optimization had to dramatically change their view about the subject. More specifically, in light of increasing interest in general purpose optimization algorithms, it has become important, to understand the relationship between the performance of an algorithm A and a given optimization problem f. Thus, the problem f became the starting point for building up a suitable algorithm. Since each optimization problem with its features, e.g. multimodality of the landscape, separability of the function, epistasis, etc., must be considered as the basis for building up an optimization solver that addresses the specific features of the problem, NFLT constitutes, in a certain sense, the “Full Employment Theorem” (FET) for optimization professionals. In computer science and mathematics, the term FET is used to refer to a theorem that shows that no algorithm can optimally perform a particular task done by some class of professionals. In this sense, as no efficient general purpose solver exists, there is always scope for improving algorithms for better performance on particular problems. Since MC, as mentioned above, represents a broad class of algorithms that combine various algorithmic components (memes), a suitable combination is necessary for a given problem. Since, during the last decade, computer scientists had to observe the features of their optimization problem in order to propose an ad hoc optimization algorithm, the approach of combining various search operators within the algorithmic design became a common practice. In this sense, the development of NFLT implicitly encouraged the use and development of MC approaches, which became extremely popular and often necessary, in computer science, at first, and in engineering and applied science, more recently, thus constituting the FET for MC.

This paper proposes a novel memetic implementation for compact algorithms. The proposed DEcDE algorithm employs a compact structure, moving operators composed of two exploitative versions of DE and a randomization of the virtual population. This randomization can be seen as an alternative search strategy that cooperates, during the evolution, with the exploitative logic of the moving operators. In other words, DEcDE performs an highly exploitative search which is periodically “disturbed” by a randomized action which perturbs the virtual population. The proposed algorithm displayed a good performance with respect to modern compact algorithms, recently proposed in literature, on a diverse set of test problems. This fact shows that the proposed MC approach is very promising, for compact algorithms, with respect to traditional MAs employing an evolutionary framework and a set of local search algorithms. Our proposal is based on the consideration that a compact algorithm, by itself, shares important similarities with a local search algorithm, and thus an algorithmic design which considers the compact algorithm as a global search algorithm can be misleading. DEcDE has also been compared with modern population-based algorithms, two of them being MC approaches. The proposed algorithm, despite its compact nature, and thus a much more modest memory requirement, displayed a respectable performance on the set of test problems considered in this study, proving thus to be competitive with complex and memory-demanding algorithms. The proposed approach has been tested on a real-world optimization problem: the on-line control of a robot manipulator for space operations in order to minimize the disturbance on the base, this base being a spacecraft or a satellite. Numerical results show that the proposed algorithm has a better performance compared to other compact algorithms in terms of both final detected solutions and convergence speed.