Incorporating kin selection in simulated annealing algorithm and its performance evaluation

Abstract

In this article, a new operator namely the kin selection operator is introduced, which significantly improves the performance of conventional simulated annealing (SA) algorithm. Inspired by a phenomenon of the same name observed in the evolutionary system, the proposed approach offers better solutions by sacrificing a solution for its `kin'. By doing so, it ensures an efficiently guided, thorough search in the neighbourhood of the best solution. Theoretical analysis is performed to show that the basic tenets of SA hold for the proposed methodology as well. Moreover, such a methodology also provides enhanced probability of survival of critical information patterns in the solution space. Experimental comparison with SA on a large number of function optimization problems is performed. In order to validate the performance of the proposed methodology over the conventional SA, a well known NP hard problem that deals with multi-level lot-sizing and scheduling problem in a PCB manufacturing firm is taken as an illustrative example.