The guided genetic algorithm and its application to the generalized assignment problem

The Guided Genetic Algorithm (GGA) is a hybrid of genetic algorithm (GA) and meta-heuristic search algorithm, Guided Local Search (GLS). It builds on the framework and robustness of GA, and integrating GLS´s conceptual simplicity and effectiveness to arrive at a flexible algorithm well meant for constraint optimization problems. GGA adds to the canonical GA the concepts of a penalty operator and fitness templates. During operation, GGA modifies both the fitness function and fitness templates of the candidate solutions based on feedback from the constraints. The Generalized Assignment Problem (GAP) is a well explored NP hard problem that has practical instances in the real world. In GAP, one has to find the optimum assignment of a set of jobs to a group of agents. However, each job can only be performed by one agent, and each agent has a work capacity. Further, assigning different jobs to different agents involve different utilities and resource requirements. These would affect the choice of job allocation. The paper reports on GGA and its successful application to the GAP