الگوریتم مصنوعی کلونی زنبور عسل برای مسئله گروه بندی حداکثر دوز های مختلف

In this paper, an artificial bee colony algorithm is proposed to solve the maximally diverse grouping problem. This complex optimisation problem consists of forming maximally diverse groups with restricted sizes from a given set of elements. The artificial bee colony algorithm is a new swarm intelligence technique based on the intelligent foraging behaviour of honeybees. The behaviour of this algorithm is determined by two search strategies: an initialisation scheme employed to construct initial solutions and a method for generating neighbouring solutions. More specifically, the proposed approach employs a greedy constructive method to accomplish the initialisation task and also employs different neighbourhood operators inspired by the iterated greedy algorithm. In addition, it incorporates an improvement procedure to enhance the intensification capability. Through an analysis of the experimental results, the highly effective performance of the proposed algorithm is shown in comparison to the current state-of-the-art algorithms which address the problem.

The maximally diverse grouping problem (MDGP) consists of partitioning a set of n elements (E) into m disjoint groups so that the diversity among the elements in each group is maximised. The diversity among the elements in a group is calculated as the sum of the dissimilarity values between each pair of elements. Let dijdij be the dissimilarity value between the elements i and j and xig=1xig=1 if the element i is in the group g and 0 if not. The problem can thus be stated as: equation(1) View the MathML sourceMaximise∑g=1m∑i=1n-1∑j=i+1ndij·xig·xjg equation(2) View the MathML sourceSubjectto∑g=1mxig=1i=1,…,n, equation(3) View the MathML sourceag⩽∑i=1nxig⩽bgg=1,…,m, equation(4) View the MathML sourcexig∈{0,1}i=1,…,n;g=1,…,m. where constraint (2) ensures that each element is located in exactly one group and constraint (3) guarantees that the number of elements contained in group g is at least agag and at most bgbg. The MDGP also appears in the literature by other names, such as the k-partition problem in Feo et al. [12] and [13] and as the equitable partition problem in O’Brien and Mingers [36]. Different real-world applications of the MDGP can be found in the literature, covering a wide variety of fields. One of the most extended applications of the MDGP is to the assignment of students to groups [4], [10], [49], [50], [51] and [53]. The MDGP also arises in further fields such as the creation of diverse peer review groups [19], the design of VLSI circuits [13], [49] and [50], the storage of large programs onto paged memory [32], and the creation of diverse groups in companies so that people from different backgrounds work together [6]. Several metaheuristic approaches were proposed to obtain high quality solutions to the MDGP. These include memetic algorithms [10] and [38], the tabu search [15], simulated annealing [38], and the variable neighbourhood search [38]. In this paper, we explore an alternative approach using the artificial bee colony (ABC) [5], [24], [26] and [27] method. The ABC algorithm is a new, population-based, metaheuristic approach inspired by the intelligent foraging behaviour of honeybee swarms. It consists of three essential components: food source positions, nectar-amount and three honeybee classes (employed bees, onlookers and scouts). Each food source position represents a feasible solution for the problem under consideration. The nectar-amount for a food source represents the quality of each solution (represented by an objective function value). Each bee-class symbolises one particular operation for generating new candidate food source positions. Specifically, employed bees search for food around the food source in their memory; meanwhile they pass their food information onto onlooker bees. Onlooker bees tend to select good food sources from those found by the employed bees, and then further search for food around the selected food source. Scout bees are a small group of employed bees that are transferred, abandoning their food sources and searching for new ones. Due to its simplicity and ease of implementation, the ABC algorithm has drawn much attention and has exhibited state-of-the-art performances for a considerable number of problems [28]. The rest of this paper is organised as follows. In Section 2 we provide an overview of particular metaheuristics that have previously been applied to the MDGP. In Section 3 we analyse the background to the ABC algorithm, which provides the basis of the specific algorithmic design we employ. In Section 4 we describe our ABC approach to the MDGP. In Section 5 we analyse the performance of the proposed ABC and draw comparisons with the existing literature. Finally, Section 6 contains a summary of results and conclusions.

In this paper, the ABC-MDGP algorithm, based on mimicking the food foraging behaviour of honeybee swarms, is proposed as a method for solving the MDGP. Our algorithm employs an initialisation scheme based on a greedy constructive method proposed for this problem and two neighbourhood operators inspired by the iterated greedy metaheuristic, which were combined with another based on swap moves. In addition, the ABC approach has been enhanced by incorporating a local improvement routine that exploits two simple local modifications of the solutions (movement and swap operations). The designed algorithm has proven to be a very high performing algorithm for the MDGP, showing itself to be very competitive with respect to state-of-the-art algorithms. These results, along with the simplicity and flexibility of the ABC approach, allow us to conclude that this metaheuristic arises as a tool of choice to face this problem. We believe that the ABC framework presented in this paper is a significant contribution, worthy of future study. We intend to explore the following two interesting avenues of research: • The employment of iterated-greedy based neighbourhood operators in ABC approaches dealing with other challenging optimisation problems. Iterated greedy has exhibited state-of-the-art performances for a considerable number of problems such as scheduling in parallel machines [11] and flowshop scheduling [14]. Thus, the development of ABC methods with iterated-greedy based neighbourhood operators for these problems seems to be a promising research field. • The study of different schemes for parallel implementations of ABC-MDGP. Parallel hardware (multicore processors, clusters, etc.) has become very affordable and widely available nowadays, favouring the parallel implementation of ABC methods [48]. We intend to implement our ABC-MDGP approach on parallel hardware, following different schemes proposed in the literature such as master–slave, multi-hive with migrations, and hybrid hierarchical [40], in order to improve results through the speed-up of the search process. These improvements are especially important when dealing with large-size instances.