Research

This research cluster is concerned with the design of systems which can themselves design other systems. If pursued and developed, it could represent a paradigm shift in the role of the system designer. The designer would design a search space where a good heuristic is likely to exist, rather than designing the heuristic itself. It would then be the job of the automated system to select and combine the components in an intelligent way.

Searching through many combinations of components is a task well suited to a computer system. We are used to computers being employed to search for a solution, with a methodology devised by us, but computers are beginning to be employed to search for search methodologies themselves.

This is a relatively young research field. The academic literature contains examples of this type of research, but it has yet to show that it can be viable in practice. LANCS therefore provides an environment where these early techniques can be researched in an environment where complex real-world problems are being addressed.

Some examples of current research in this area are shown below.

Automatic Design of Constructive Heuristics

Constructive heuristics start from an empty solution, and build it up, element by element. An example is a packing problem where you begin with an empty container, into which you place one piece at a time. Heuristics are used to decide which piece to place next and where to place it, and a the choice of heuristic can mean the difference between a very bad solution and a very good one.The heuristics are usually quick, as they fix the position of an item once it has been placed. Another example is the scheduling of a number of exams into a timetable. In this case, the constructive heuristic will place the exams one at a time into the remaining space, until all of the exams have been scheduled.

Constructive heuristics have been the subject of research for decades, and they have been analysed and tested extensively. The latest constructive heuristics for some problems are the result of decades of research, where each heuristic has improved upon the last. It is possible for computers to automatically design constructive heuristics, which are competitive with those that are human-designed.

Results:

The following links provide details of studies which have been performed on this topic.

Automatic Design of Constructive Heuristics for One-Dimensional Packing

Automatic Design of Constructive Heuristics for Two Dimensional Strip Packing

Automatic Design of Metaheuristics

This research area is a natural progression from the automatic design of constructive heuristics.

Genetic programming approaches have been employed in the literature to automatically design constructive heuristics for cutting and packing problems. These heuristics can obtain results superior to human created constructive heuristics, but they do not generally obtain results of the same quality as metaheuristics, which start from an initial solution and iteratively improve it.

The automatic design of the neighbourhood move operator within a metaheuristic is a natural progression from the automatic design of constructive heuristics, and increases the quality of solutions which can be obtained by an automatically designed system.

If metaheuristics can be successfully designed, in addition to a constructive heuristic which initialises the solution, then the quality of results which can be obtained by automatically generated algorithms can be significantly improved.

Results:

The link shows details of a recent study on this topic.

Automatic Design of Local Search Operators for One-Dimensional Packing