A new hybrid genetic algorithm for the maximally diverse grouping problem
- PDF / 4,242,112 Bytes
- 20 Pages / 595.276 x 790.866 pts Page_size
- 2 Downloads / 221 Views
ORIGINAL ARTICLE
A new hybrid genetic algorithm for the maximally diverse grouping problem Kavita Singh1 · Shyam Sundar1 Received: 28 May 2018 / Accepted: 26 December 2018 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract This paper presents a new hybrid approach ( SGGA) combining steady-state grouping genetic algorithm with a local search for the maximally diverse grouping problem (MDGP) related to equal group-size. The MDGP is a well-known -Hard combinatorial optimization problem and finds numerous applications in real world. SGGA employs particularly (a) crossover operator (b) the effective way of utilization of local search and (c) the additional replacement strategy, making it different from the existing genetic algorithm for the MDGP. On a set of large benchmark instances, SGGA is competitive in comparison to the existing best-known approaches in the literature and performs particularly well on large-size instances. Some important ingredients of SGGA that shed some light on the adequacy of SGGA are analyzed. Keywords Maximally diverse grouping problem · Steady-state genetic algorithm · Crossover · Replacement strategy · Local search
1 Introduction Maximize ∶ The maximally diverse grouping problem (MDGP) is a wellknown -Hard combinatorial optimization problem [7]. Given an undirected, complete and edge-weighted graph G = (V, E, w) , where V = {1, 2, 3, … , n} is the set of n vertices; E is the set of edges; and w = {dij ≥ 0 ∶ {i, j} ∈ E} is the set of non-negative edge weights, the MDGP aims to partition the vertex set V into k disjoint groups in such a way that the sum of edge weights of k groups is maximized while respecting the size (Size) of each group that consists of same number of elements with Size = nk . In another variant of this problem, the size of each group Size lies in the interval [ ag , bg ], where ag ≤ bg for g = 1, 2, … , k . Note that a vertex i ∈ V is referred to as an element, while the weight dij of an edge is referred to as the diversity between i and j elements. Mathematically, the MDGP can be formulated as:
* Shyam Sundar [email protected] Kavita Singh [email protected] 1
Department of Computer Applications, National Institute of Technology Raipur, Raipur 492010, India
k n−1 n ∑ ∑∑
dij xig xjg
(1)
i = {1, 2, 3, … , n}
(2)
g=1 i=1 j=i+1
Subject to : k ∑
xig = 1
for
g=1
n ∑
xig = Size
for
(3)
g = {1, 2, 3, … , k}
i=1
(4) where xig is a binary variable and if the element i is in group g, then xig = 1 , otherwise 0. Constraint 2 forces that only one element will be present in exactly one group. Constraint 3 ensures that the size of each group g is Size. Hereafter, vertices and elements are used interchangeably in this paper. The MDGP finds numerous applications in real world such as creation of student work groups [12, 24], formation of diverse groups in order to ensure that projects are evaluated from several different points of view [2], VLSI design [21], storage allocation of large programs onto paged me
Data Loading...
