FRACTOP: A Geometric Partitioning Metaheuristic for Global Optimization

Abstract

We propose a new metaheuristic, FRACTOP, for global optimization. FRACTOP is based on the geometric partitioning of the feasible region so that search metaheuristics such as Simulated Annealing (SA), or Genetic Algorithms (GA) which are activated in smaller subregions, have increased reliability in locating the global optimum. FRACTOP is able to incorporate any search heuristic devised for global optimization. The main contribution of FRACTOP is that it provides an intelligent guidance (through fuzzy measures) in locating the subregion containing the global optimum solution for the search heuristics imbedded in it. By executing the search in nonoverlapping subregions, FRACTOP eliminates the repetitive visits of the search heuristics to the same local area and furthermore, it becomes amenable for parallel processing. As FRACTOP conducts the search deeper into smaller subregions, many unpromising subregions are discarded from the feasible region. Thus, the initial feasible region gains a fractal structure with many space gaps which economizes on computation time. Computational experiments with FRACTOP indicate that the metaheuristic improves significantly the results obtained by random search (RS), SA and GA.