Given a number of example problems, FAIME will design metaheuristics tailored by modifying their source code. Compared to human designed metaheuristics, these will be better, faster and stronger. Pilot studies indicate they will perform better than human designed metaheuristics, as we are using them as a starting point. They will be designed faster than via the manual design process. We will able to make stronger statistical statements about their properties. In short, we will employ a machine learning approach to design metaheuristics, explore how features can be used to make predictions, and how effectively we can design metaheuristics given a problem's features.
There are three broad types of computational problems; easy (tractable), hard (intractable), and impossible (incomputable). These problems are challenging purely because of the astronomical number of possible solutions and trying every possibility would require an infeasible amount of time. Metaheuristics tackle the hard problems, mitigating this issue by sampling a tiny subset of the possibilities. One drawback is that there is no guarantee of performance. FAIME will examine the efficacy of automatically designing metaheuristics, along with key performance indicators of the metaheuristics, such as scalability, tolerance, robustness, convergence.
There are issues with current practices in metaheuristic research which we plan to tackle directly. These include the following:
-There are few principles to assist with the design of metaheuristics, making it a trial and error process. A feature based approach will provide a framework against which to address this.
-There is an explosion in the number of published metaheuristics, in particular metaphorically inspired ones, with few guidelines to select among them. A feature based approach can provide a basis offering some guidance.
-Metaheuristics are often designed in isolation from the problems they will be applied to. FAIME will use feedback from the example problems to inform the design process.
Also, manually designing metaheuristics has its limitations. While it does produce better performing metaheuristics, it does not contribute to an understanding of how to produce better metaheuristics. FAIME drives deeper by automatically generating metaheuristics and then using features to provide a framework for classification, providing a basis to understand their design.
This FAIME project will
-automatically designs metaheuristics for example problems using a factory consisting of two levels, a generating-level and a test-level which generates and tests metaheuristics. The metaheuristics will be generated by modifying their source code, and then tested on a set of problems. We will
-investigate the properties of the metaheuristics (scalability, tolerance, robustness, convergence).
-employ a recent technique which takes existing source code and improves it.
-be implemented on parallel machines, which are ideally suited to the design process.
-draw on computability theory, probability theory, and other recent mathematical results to inform the design process and feature based approach.
We do not yet have an effective classification scheme for metaheuristics and problems. A classification scheme which reflects the relationships of entities being classified brings clarity and allows predictions to be made. Using the feature based classification scheme, we will investigate the accuracy of predictions we can make about metaheuristics and problems. We aim to be able to make statistical statements about the performance of metaheuristics such as, metaheuristic H will deliver a solution of quality X units, with tolerance +/- Y units, within Z time units, thus offering some indication of performance and which metaheuristic to choose for which problem.
|