Memetic Algorithms for Solving Very Complex Optimization Problems

Dear Colleagues,

Engineering, including social, agricultural, management, etc., engineering and other applied fields, very often faces problems that are theoretically unsolvable in the mathematical sense, as they belong to the intractable NP-hard (non-polynomial) complexity class, or even for polynomial class problems, the exponent is too high and thus a theoretically acceptable solver leads to an algorithm that will not deliver results in any reasonable time. This is not an effect of “too slow” or “too small capacity” computers, such as the hypothetical “galactic computer” that would have the size of the galaxy, in the sense that each atom would be a computing unit that would operate with the speed of light but still could not deliver guaranteed results for even moderately large-sized real problems within the total time elapsed since the Big Bang .

How come that such “unsolvable tasks” can nevertheless be tackled in real life by various intuitive and expert approaches? Instead of looking for an exact solution, engineers and other applied specialists are satisfied with near-optimal and almost-sure solutions. In the control of non-linear systems, which occurs rather commonly in every field of industry, linear model approximations or stable expert approaches are applied. In the optimization of routing, scheduling, or packing, heuristic algorithms are developed, which are able to handle extremely large instances in the order of millions of nodes or agents. Many of these heuristic and approximate approaches are tailor made and suitable only for a single type of task, or for a very narrow class of problems. However, as always new problems emerge, and new extensions or modifications of the existing tasks have to be solved, it is necessary that approaches and algorithms of “universal” applicability are studied.

Evolutionary algorithms, one of the three main components of computational intelligence, offer at first attempt a rather good answer to these problems. Their basic idea is to mimic the natural evolution of living beings, by applying two elements: the random strategy of mutation, and the advantageous combination of existing candidates for a good solution by cross breeding, exchanging the “genes” or “chromosomes” of more or less acceptable candidates for an optimal solution. However, evolutionary algorithms have the tempting property of being global in the search for optimal solutions; the difficulty caused by this globality is the slowness of the convergence to an acceptably optimal solution.

On the other hand, in traditional mathematics, there are methods for optimizing functions, graph searches, etc. The great disadvantage of such methods, like gradient-type optimization, e.g., Levenberg–Marquardt (LM) optimization, is that they always go to the nearest optimum. However, they are rather fast and efficient. Thus, they are the most suitable approaches for local searches of the optimum.

P. Moscato had the brilliant idea to combine the advantages of both the global search using the evolutionary (genetic) method and the local search using a traditional gradient-type approach. As a result, a new class of more efficient, faster, and more precise algorithms was created: memetic algorithms. Here, both advantages are combined: the evolutionary part provides global search and the traditional part very fast local search. The latter is nested into the cycles of the former. Later, some generalizations of Moscato’s original idea were proposed and a wider class of memetic algorithms was proposed where the outer cycle is an arbitrary evolutionary- or population-based optimization technique and the inner cycle (or even, cycles) use any traditional local search method, including discrete ones, like 2-opt, etc.

These approaches led to rather good results, e.g., the Guest Editor’s team combined Nawa and Furuhashi’s Bacterial Evolutionary Algorithm with LM, or, in discrete cases, subsequent 2-opt and 3-opt, and achieved rather generally applicable and efficient new algorithms.

This Special Issue is dedicated to memetic algorithms in the widest sense. Papers on new techniques, or new combinations of techniques, proposing novel memetic algorithms are very welcome, where there is a novelty element in the approach itself or in the way of applying it for a certain class of problems. It is very important, however, that the novelty and the value of the proposed new approaches is validated. There are many data depositories for various benchmark problems (function optimization, mechanical, chemical, and other control systems; and graph search, scheduling, bin packing, and similar discrete NP-hard tasks). The condition of acceptance is that at least one of the following criteria is satisfied:

The new method is

-           More efficient (faster or more precise, or in some sense better in a well-motivated evaluation sense);

-           More predictable in the run time than previous approaches;

-           More general (“universal”) in terms of applicability.

It is possible that a combination of a memetic and one or more other type (evolutionary, traditional, etc.) algorithm(s) could be combined, assuming that one of the above criteria is satisfied . Thus, research papers where scheduling algorithms for alternating optimization periods are presented are welcome—if at least one of the components is a memetic approach.

Authors are encouraged to refer to benchmark data repositories and present sufficiently large and complex problems to support their claims.

Prof. Dr. László T. Kóczy
Dr. Carlos Cotta
Dr. Aleksander Byrski
Dr. Kevin Wong
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.