A Fast Implementation Of Memetic Algorithm For The Max-bisection Problem

Max-bisection problem is an important topic in graph theory and combinatorial optimization. Max-bisection problem of a weighted graph G= (V, E) is to partition the vertex set V into two subsets that have equal cardinality, such that the sum of the weights of the edges between them is maximized. It plays an important role in both theoretical models and practical experiments. Max-bisection is widely applied in various areas, such as sparse matrix computation and VLSI design. In general, it is an NP-complete problem and has been extensively studied.In this work, a fast and effective memetic algorithm has been proposed for this problem, which consists of a greedy-based crossover operator, a fast local search pro-cedure and a population updating procedure. Firstly, we overview basic definitions and notations in graph theory, introduces backgrounds and the current situations of several related problems. Afterwards, we discuss our memetic algorithm in detail, and report the experimental results on G-set instances.Our memetic is to repeat alternately a crossover to generate a new solution and a local search to improve it. At the beginning, each individual in the initial population is generated by the randomized algorithm and improved by the local search. During each generation, two individuals are firstly selected randomly as parents from the population. At least half of vertices are equally assigned to two subsets by performing crossover. Then we combine the structural information of the fixed vertices to deal with the unfixed vertices. Caring for the need of maximizing the cut, when an unfixed vertex is added to a certain subset, we greedily choose one which contributes to the sum of weights of external edges as many as possible and the sum of weights of inner edges as few as possible. This process alternates repeatedly between the two subsets until there is no unfixed vertices left. Thus we obtain a new individual and it obviously satisfies equal sized constraint.The local search procedure is based on KL and FM algorithms. The basic operation is to find the vertex-swapping with maximum increment in the cut value. They are locked in case that they are swapped again in this pass. In order to escape from local optima, it is acceptable that current increment is negative. The initial algorithms attempt to repeat it for n/2-1 times to find a better solution in every pass. Unlocking all the vertices and resetting the initial solution which is the best solution in this pass, the next pass continues. When it fails to find a better solution in this pass, the algorithms terminates.Typically, the most improvements arise in previous several operations. In ad-dition, the algorithms may waste a lot of time and easily get stuck in a bad local optimal solution if too many vertices are moved in every pass. Therefore, the basic operation repeats only [nγ] (0<γ<1/2) times in every pass. The parameter γ is set to 1/6 by performing preliminary experiment.After generating a new individual in the crossover, it is improved by the above local search. At last, it is determined whether to be inserted into the population or not and which existing individual is replaced by the population updating proce-dure. A function h(x) is defined to measure the solution x. It takes into account both quality and diversity of the solutions x. Firstly, a temporary population P’ is constructed by inserting the new offspring x0 into primary population P. Secondly, the function value h(xi) of each individual xi is calculated and we find xmin-i with minimum score among primary population P. If its score is not better than x0, then P is updated by replacing xmin_i by x0; otherwise, x0 replaces xmin_i with probabil-ity pr. With the aid of the above procedure, we achieve dynamical control of the population P.After the memetic algorithm generates a great many offsprings, the solutions may be very similar in the population, i.e., its diversity is poor. So a simple perturba-tion operation is applied to diversify the search with a probability. The perturbation operation randomly selects [n/10] vertices from each subset of the new offspring x0 generated by crossover, respectively. And then swaps them. It is improved by local search after that.Experiments are performed on 71 G-set graphs. The results show that the proposed algorithm can find very competitive results, and is 20 to 130 times faster than Wu and Hao’s memetic algorithm which is the best known algorithm for max-bisection on middle-scale and large-scale instances. Moreover, some current best known solutions are improved.