Greedy Randomized Adaptive Search Procedure English Language Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Network or graph is simply points connected to each other by lines. The points are the entities and connecting line represents relationships between entities. A graph G = (V, E) is simply defined by set of vertices (V) and set of edges (E) between pair of vertices. Figure 1 illustrates a simple network or graph, the set {1,2,3,4,5,6} is a vertex set (V) and set {(1,2), (1,4), (2,3), (3,6), (4,5), (5,6)} is a edge set (E). Some of the networks as follows, electrical and power networks, wireless network, logical network, transportation networks, rail and airline service networks, telecommunication networks, social networks, computer networks, biological networks and many more.

Figure 1: Illustration of a simple network

"A social network is usually represented by a graph, in which the set of vertices corresponds to the "actors" in a social network and the edges correspond to the "ties" between them" [Scott, 2000]. Actors can be a people or groups of people, organizations and examples of tie between a people or groups of people can be a relationship and between organizations can be various transactions between them. Social Network Analysis is a tool in modern sociology and studies social behavior of the individuals, organizations and other kind of entities. Thus, social networks can be easily and conveniently modeled as a graph to study and analyze the behavior of social systems. Some examples of social networks are MySpace, LinkedIn, Orkut and Facebook etc.

This thesis studies the "maximum co-k-plex problem" (MCPP-k), which is a relaxation of maximum stable set problem (MSSP) that is well known in combinatorial optimization. This problem was introduced as a "maximum k-dependent set problem" [1]. The maximum stable set problem is similar to find a maximum co-1-plex in G. The maximum co-k-plex problem finds a maximum cardinality co-k-plex in a graph G. Problem Definition: Let k be a positive integer. A co-k-plex set in an undirected of graph G = (V, E) is a subset of the set V of vertices such that no vertex in the subset is adjacent to more than k-1 vertices of the subset, i.e. the co-k-plex is an induced subgraph in which each node has at the most k-1 degree. A co-1-plex set in G is simply collection of nonadjacent vertices in G, i.e. an independent set. Furthermore, co-2-plex set is in general a set of independent vertices and edges and co-3-plex set is a set of independent vertices, paths and cycles. The maximum independent set is important for applications in Computer science, Operation research, Map labeling, molecular biology, scheduling, coding theory, graph coloring, assigning channels to radio station, and register allocation in a compiler. The motivation behind such problem is that the independent set has no edge between any two vertices in a set. These parameterized model represent independent set when parameter k = 1 and provide an independent set relaxation for k > 1 as increase of the value of k corresponds to a gradual relaxation of independence.

The maximum co-k-plex problem and maximum k-plex problem are closely related and equivalent in graph complementation, i.e. finding maximum co-k-plex in G is equivalent to finding maximum k-plex in . So, we can find maximum co-k-plex problem applications in clustering and mining biological networks, internet graphs, stock market graphs and wireless networks

1.2 CONTRIBUTION:

Broadly this thesis makes the following contributions:

Performed literature survey of graph theory, social networks analysis, clique and its relaxation, especially degree based model co-k-plex which relates independent set.

Performed literature survey of combinatorial optimization and various metaheuristics which are used to solve large combinatorial optimization problems.

Developed metaheuristic algorithms to solve maximum co-k-plex problem because it is a NP-hard problem and no such metaheuristic algorithm had been used to solve this problem.

Studied, designed and developed problem specific greedy randomized construction phase for underlying research problem.

Studied and design neighborhood definition in local search to imrove effectiveness of the local search.

Developed greedy randomized adaptive search procedure (GRASP) algorithm to solve maximum co-k-plex problem in C++.

Conducted preliminary experiments on C++ implementation to discover ways for speeding up algorithm to reduce computational time.

1.4 ORGANIZATION:

The remainder of this thesis is organized as follows: Chapter two presents extensive background on required notations, definitions from graph theory, and review of relevant literature on cliques and its extension models, independent sets, co-k-plex sets and relationships among these sets.

Chapter three introduces combinatorial optimization and need of metaheurictics algorithms to solve combinatorial optimization problems. Also some metaheuristic algorithms studied extensively like Iterated Local Search (ILS), Simulated Annealing (SA), Tabu Search (TS), Genetic Algorithms (GA) and Greedy Randomized Search Procedures (GRASP) etc.

In chapter four, we studied GRASP metaheuristic algorithm and design problem specific construction phase. We define neighborhood structure and local search improving technique for local search phase.

Chapter five gives brief idea about research activities and thesis plan.

2.1 DEFINITION, NOTATION AND BACKGROUND:

Consider a simple, finite graph G is a pair (V, E), where V is a set of vertices, and E is a set of edges between the vertices E âŠ† {{u,v} | u, v âˆˆ V}. Graph G is called to be undirected when edges in G have no orientation, i.e. they are not ordered pairs. Let G = (V,E) be a undirected graph representing a social network, deg G() = |{ u : (u,) E}| denote the degree of in G. dG(u, ) denote the length of a shortest path in terms of number of edges between vertices u and in G, and diam(G) = max dG(u, ) (u, ) V is the diameter of graph G. G[S] = (S, E (S S)), denotes the subgraph induced by S V. N() denotes the set of vertices which are adjacent to in graph G, i.e. number of edges incident at . A complement graph = (V,) of the graph G is a graph with the same vertices as G and with the property that two vertices in  are adjacent if and only if they are not adjacent in G, i.e. e , e E.

2.1.1 CLIQUE:

Definition 2.1: A subset of vertices S of a graph G = (V, E) is a clique if, there is an edge for each pair of vertices. A graph G = (V,E) is complete graph if its vertices are pairwise adjacent, i.e. i, j V, {i, j} E, i.e. a clique is a complete graph. A clique is called as a maximal clique if it is not contained in any other clique. Maximum clique in a graph G is a clique of maximum cardinality in a graph G and the maximum clique number is Ï‰(G). The maximum clique problem is known to be NP-complete [11]. Figure 2.1 illustrates a complete subgraph or a clique for 2, 3, 6 nodes respectively.

Figure 2.1: Illustration of Clique

Clique definition is restrictive in real life situations. So, alternative approaches were suggested to overcome drawbacks related to clique in order to relax the clique concepts, such as k-clique, k-club, k-clan and k-plex.

2.1.2 K-CLIQUE:

Luce [1950] introduced the distance based model called k-clique, where the maximum length of shortest path between each pair of vertices is at the most k.

Definition 2.2: A subset of vertices S of a graph G = (V, E) is a k-clique if,

dG(u, ) k u, S

In other words, we can reach to a node from any node in a original graph in at the most k distance. 1-Clique is a clique because the shortest distance between all pairs of vertices is one. In k-clique, we find maximum shortest path between the nodes in a subgraph by looking at the original graph. In other words, the nodes corresponding to a shortest path between two nodes may not belong to the induced subgraph k-clique. This weakness is common to k-clique, so the concept of k-club, a degree based model [Alba, 1973] is introduced by bounding the diameter of the induced subgraph. Figure 2.2 illustrates relaxation of clique based on the increasing value of k = 1, 2, 3. The set {1-2-5} is a 1-clique, set {1-2-3-4-5} is a 2-clique and graph is a 3-clique.

Figure 2.2: Illustration of k-clique concept

2.1.3 K-CLUB:

Definition 2.3: A subset of vertices S of a graph G = (V, E) is a k-club if,

diam(G[S]) k

In other words, diameter of a subgraph is at the most the value of k. Every k-club is a k-clique but converge is not true always. This is illustrated in Figure 2.3: the set {2-3-4-5-6} is a 2-clique in (a) but not a 2-club as the induced subgraph (b) has diameter 3.

(b)

Figure 2.3: (a) Undirected network (b) Induced subgraph G[S]

The maximum k-club problem finds a k-club of maximum cardinality in a graph G and the maximum k-club number is «(‡).

2.1.4 K-PLEX:

An alternate way of relaxing clique is a degree based model k-plex which was first introduced by Seidman and Foster [1978].

Definition 2.4: A subset of vertices S of a graph G = (V,E) is a k-plex if,

deg G[S]() = | N( S | |S| - k v S.

In other words, a subset of vertices of a G is said to be k-plex if the degree of every vertex in the induced subgraph G[S] is at least |S| - k. The k-plex is maximal, if it is not contained in any other k-plex. 1-plex is always a clique. In Figure 2.4, the sets {1,2,3,4}, {2,3,4,6},{1,3,4,5} are 1-plex (clique), sets {1,2,3,4,5} and {1,2,3,4,6} are 2-plexes and the graph is a 3-plex.

Figure 2.4: Illustration of k-plexes

2.1.5 INDEPENDENT SET:

Clique is equivalent to an independent set is in the complementary graph. An independent set is a subset of pair wise non adjacent vertices in G = (V,E). S V is an independent set in G if and only if it forms a clique in the complement graph = (V,).

Definition 2.5: An independent set I is a subset of vertices such that for all i, j I, (i, j) E.

The independent set is said to be maximal if it is not contained in any other independent set. The maximum independent set problem (MIS) is to find an independent set of maximum cardinality in a graph G and the independence number, Î±(G), is the cardinality of a maximum independent set. Figure 2.5 illustrates this concept: The set {1, 2} is a maximal independent set and set {3,4,5} is maximum independent set with Î±(G)=3.

Figure 2.5: Illustration of Maximum independent set and maximum co-k-plex set

2.1.6 CO-K-PLEX:

Definition 2.6 [2]: A subset of vertices S of a graph G = (V, E) a co-k-plex if,

deg G[s] () = | N() S | k-1 Ð„ S.

That is, the co-k-plex is an induced subgraph in which degree of a Ð„ S in G[S] is at the most k-1, i.e. G[S] has maximum degree of k-1 or less. A co-1-plex is the complement of a 1-plex and is therefore similar to a stable set. Figure 2.5 illustrates of co-k-plex concept: the set {3-4-5} is a maximum co-1-plex (independent set) and also a maximum co-2-plex and sets {1-2-3-4}, {1-2-4-5} are co-3-plex. The maximum co-k-plex problem finds maximum cardinality co-k-plex in G and the co-k-plex number, Î±k(G) is the cardinality of a maximum co-k-plex in G.

The maximum clique problem (MCP) is closely related to MSSP. The MCP finds overly restrictive cohesive subgroups i.e. extremely cohesive subgraphs. Therefore, this approach fails to detect much structure present in a graph. To address this issue, Seidman and Foster introduced k-plex approach to find degree bounded cohesive subgraphs in 1978. The k-plexes are cohesive subgraphs which were introduced to relax the structure of cliques. The co-k-plex and k-plex are equivalent in graph complementation, i.e. the set S is a co-k-plex in G if and only if S is a k-plex in . Consequently, the maximum co-k-plex and maximum k-plex problems are closely related. This is analogous to the relationship between stable sets in G and complete graphs in .

Co-k-plex is a relaxation of independent set depending on k value. By increasing k value we can obtain k degree bounded less cohesive subgraphs. As the maximum co-k-plex problem is NP-hard problem, we use greedy randomized adaptive search procedure (GRASP) metaheuristc algorithm to solve this problem. Next chapter, we study few popular metaheuristic algorithms and give a brief introduction to GRASP.

3.1 INTRODUCTION TO METAHEURISTICS:

Optimization problems of both practical and theoretical importance are divided into two categories: those with continuous variables and those with discrete variables. Combinatorial Optimization (CO) problems fall into a category of problems with discrete values for feasible solutions. In such class of problems, we are looking for an object from a finite, or possibly countable infinite, set of maximum or minimum objective value. Some well known Examples of CO problems are the Travelling Salesman problem (TSP), the Quadratic Assignment problem (QAP), Timetabling and Scheduling problems.

Definition 3.1: A combinatorial optimization (CO) problem is described by a pair (S,) where an objective function to be minimized or maximized as per problem definition and S is a feasible search space; each element of S can be a candidate solution. To solve a combinatorial optimization problem, we need to find a solution set s* S with minimum or maximum objective function value. i.e. (s*) (s) for minimization problem and (s*) (s) for maximization problem s S. s* is globally optimal solution of (S,).

Practical importance of the CO problems has increased over past two decades. Hence to solve such problems exact and heuristic algorithms have been developed and studied. Exact algorithms are guaranteed to provide an optimal solution in finite steps for every finite size instance of a CO problem. Most of the CO problems are categorized as NP-hard (no polynomial time algorithm exist to solve them, assuming that ). Therefore, exact algorithms might need exponential time in worst-case which increases computational time in practice considerably. Heuristic algorithms find a good solution instead of finding optimal solution in a significantly reduced amount of time. Basic heuristic algorithms are usually distinguished as constructive and local search methods. Constructive algorithms generate a feasible solution starting from an empty solution by exploring search space and local search algorithms iteratively try to find better solution to replace starting solution by exploiting the search space intensively in the neighborhood of starting solution. The neighborhood structure is formally defined as follows:

Definition 3.2 [3]: A neighborhood structure is a function : S ƒ  2s that assigns to every s S set of neighbors (s) S. (s) is called the neighborhood of s.

Then local minima can be defined as follows:

Definition 3.3 [3]: A locally minimal solution with respect to a neighborhood structure is a solution such that s : () (s). We call a strict locally minimal solution if () (s) s , s

Last two decades, new approximate methods are emerged which combine basic heuristic methods to enhance search process. These methods are called as Metaheuristics. Metaheuristics are widely used to solve combinatorial optimization problem because of their simplicity and robustness. Metaheuristics produce good solutions in a reduced amount of time for complex combinatorial problems which requires higher computational time to solve them to optimality in worse-case. Metaheuristics are not problem specific and return good solutions by efficiently exploring neighborhood in short amount of computational time even if problem structure is changed.

Performance of the metaheuristics algorithms are dependent on how effectively algorithm is designed to do exploration and exploitation of the search space. Therefore every metaheuristic algorithm should be carefully designed with such aim. Thus, "Intensification and Diversification" (I&D) are the most powerful and effective factors driving metaheuristics performance to high level. Glover and Laguna in 1997 provided high level descriptions of intensification and diversification in [9]. In intensification, algorithm explores search space for high quality solutions in the neighborhood and in diversification moves to unexplored search space to find better solutions than what are found in exploration in intensification. The move in search space greatly depends on the search philosophy of a metaheuristic itself and the criterion defined by the problem. Therefore, one has to keep in mind to have right balance between intensification and diversification to obtain an effective metaheuristic.

In recent years, researchers have been trying to find out hybrid metaheuristics to increase efficiency and effectiveness of algorithms based on metaheuristics. Hybridization is made by combining different metaheuristics. Iterated Local Search (ILS), Simulated Annealing (SA), Tabu Search (TS), Greedy Randomized Search Procedures (GRASP), Genetic Algorithms (GA) and Variable Neighborhood Search (VNS) are some of the metaheuristics used to solve large CO problems.

3.1.1 ITERATIVE LOCAL SEARCH:

Local search is an iterative improvement, as each move is performed only when a better solution is found than a current solution in a search space. Initial feasible solution is generated randomly and local search is applied on randomly generated solution. Algorithm terminates as it finds locally optimal solution.

Function Improvesolution(N(s)) explores and find a improving solution if one exists in the neighborhood of current solution. Function Improvesolution(N(s)) can return first improving or most improving solution or any intermediate function. Thus performance of the local search depends upon the initial feasible solution, objective function and neighborhood definition.

S ƒŸ ConstructIitialSolution()

while s is not loacally optimal

s'ƒŸ Improvesolution(N(s))

s ƒŸ '

end while

Figure 3.1: Pseudo code for local search

Local search has a tendency to be trapped in a local optimum solution. Therefore several techniques have been developed to prevent algorithms from being trapped in a local minimum by selecting inferior solutions and other mechanisms to avoid local minima.

3.1.2 SIMULATED ANNEALING:

Simulated Annealing is one of the stochastic local search methods that accept worse solution to avoid local minima which is used to solve combinatorial optimization problems [15], [12]. The move from current solution to worse solution is governed by a probabilistic function which depends on difference between current and encountered worse solution (f(s') - f(s)) and temperature parameter (T). The algorithm terminates when it meets the termination criterion. The termination criterion could be no improvement in current solution and may be user defined critical value for best solution.

The algorithm starts with a construction of an initial solution (s) (can be constructed randomly or by using some heuristic methods) and setting a temperature parameter. At each iteration a solution s' Ð„ N(S) is randomly constructed and accepted as a new solution depending on f(s), f(s') and T. s is replace by new solution s' if f(s') < f(s), otherwise acceptance of the new solution is depend on probability. The probability is usually computed by Boltzmann distribution exp ((f(s')-f(s))/T).

S ƒŸ ConstructIitialSolution()

T ƒŸ Set Initial Temperature Parameter

N ƒŸ 0

while loop condition not met do

s' ƒŸ SelectRandom(N(s))

If f(s') < f(s) then

s ƒŸ s'

else

Accept s' as new solution by probability (f(s), f(s'), Tn)

endIf

T n+1 ƒŸ UpdateT (Tn, f(s'), f(s))

n ƒŸ n+1

end while

Figure 3.2: Pseudo code for Simulating Annealing algorithm

Initially the controlled temperature parameter is set to a high value which provides high acceptance to worse solution called as uphill moves. Typically, temperature parameter is gradually decreased in successive iterations during search process.

This algorithmic approach is analogous to the physical annealing process in metallurgy. Thus the effectiveness of the algorithm is depending on the cooling schedule. The value of T is determined [10]. Slow cooling schedule can be guaranteed to find global minima for certain CO problems, but in practice it is not feasible. Thus faster cooling schedules are adopted in practice.

3.1.3 TABU SEARCH:

Tabu search [6] [7] [8] method uses memory structure which stores a potential solution when it is encountered during local search. Such short term memory is used to avoid cycling (revisiting the previous solutions) to enhance the local search. This memory structure is called as taboo list, in which recently encountered solution is stored and enhancement in algorithm is achieved by avoiding moves toward such solutions.

S ƒŸ ConstructInitialSolution()

TabuList ƒŸ

AllowedSet ƒŸ

While loop condition not met do

S' ƒŸ ConstructNewSolution(s)

If (s' Ð„ N(s) | s' does not satisfy tabu condition

or s' satisfies at least one aspiration condition)

AllowedSet ƒŸ AllowedSet s'

endIf

s ƒŸ SelectBestSolution(AllowedSet)

Update TabuList and Aspiration conditions()

endwhile

Figure 3.3: Pseudo code for Tabu Search

Algorithm starts with construction of initial solution, empty tabu list and allowed set. New solutions are constructed by exploring neighborhood of current solution. Allowed set list is constructed by adding newly constructed solutions by checking tabu list. When a potential solution is found, it is stored in a tabu list and previously stored solution is removed from tabu list if it has remained in the list for a prespecified number of iterations. The best solution among allowed set solutions is kept as current solution followed by updating aspiration conditions. Algorithm terminates when termination condition is met.

The tabu list prevents algorithm to cycle by not returning to recently visited solutions. Enhancement of local search depends on the length of tabu list. Large tabu list allow algorithm to explore larger region in the neighbor of the current solution and smaller region in case of small tabu list.

Furthermore, solutions attributes are stored instead of storing solutions due to memory considerations. Attributes are usually components of the solutions. More than one attribute can be defined and a separate tabu list is maintained for each attribute. Such tabu lists are called tabu conditions which are used to manipulate allowed set. There is loss of information when attribute is stored instead of solution. Thus the possibility of not choosing potential solution in allowed set arises. Hence to reduce such possibility some aspiration conditions are maintained to accept solution in allowed set even if it is not satisfied by tabu conditions.

3.1.4 GENETIC ALGORITHM:

Origin of formal genetic algorithms dates back to 1970s and was developed by John Holland University, Michigan. As the name suggests, it emulates the biological evolutionary process. Biology explains that a gene forms the basic building block of any living organism. These genes are connected together to form chromosomes. These chromosomes recombine to reproduce new chromosomes. Every one of us has different physical and mental attributes because of the difference in genetic structures we carry. Before understanding genetic algorithm, it's essential we go through some of the definitions-

a) Crossover rate: Given two chromosomes (or string of bits) crossover rate simply represents a random position after which we flip the bits of the strings. For instance if we have two strings A and B as follows,

A= 1 0 0 1 0 0 1

B=1 0 1 1 0 1 0

Say the random position selected is 4 and so all the elements after 4th position will get interchanged. New chromosomes will look like-

A= 1 0 0 1 0 1 0

B= 1 0 1 1 0 0 1

b) Mutation rate: Mutation rate represents the probability that the bits get flipped within a chromosome. In a binary coded bit, 0 become 1 and 1 becomes 0.

Genetic algorithm can be summarized in following steps:

1) A large sample of chromosomes (or solutions in CO) will be generated using some intelligent heuristic or at random.

2) Every chromosome will receive a fitness score based on its evaluation on our objective function.

3) After getting a fitness score, we select two chromosomes at random as "parent" chromosomes. These are used further to reproduce new chromosomes. The selection for parent chromosomes is usually at random. There are many ways to do this. Roulette wheel selection and Tournament selection are two popular methods to do this.

4) Once the parent chromosomes are selected, based on the crossover rate, the bits are interchanged as explained above.

5) New parent chromosomes obtained after crossover are then mutated based on the mutation rate.

6) Finally, these parent chromosomes recombine themselves to produce new offspring (solution).

This process of reproduction continues until we recreate a new sample population as we had created earlier for the first iteration. Now as explained in step 3 Roulette wheels election is explained as below-

Roulette Wheel selection: Let's represent the entire fitness score for all chromosomes on a pie chart or a roulette wheel. Every chromosome will get a share equivalent to its fitness score. Selection of parent chromosome is the done by just spinning this wheel and picking up the chromosome which stops at some predefined point. This method does not guarantee that the top chromosomes (with best fitness score) will get selected but just that they have a very good chance of selection.

Genetic algorithms will end upon meeting the predefined termination conditions. This termination condition can be anything like limit on computational resources or maximum number of iterations. It depends on the problem at hand. Or if we already know some upper bond on the solution of the problem at hand, this too can be one of the termination criterions.

3.1.5 GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE (GRASP):

GRASP is a multistart metaheuristic used to solve combinatorial optimization problems [13] [14]. An iteration of the GRASP consists of two phases: greedy randomized construction phase and a local search phase. During the construction phase, a initial feasible solution is built and local minimum (locally optimal solution) is found by investigating neighborhood of the initial feasible solution in local search phase. The best solution encountered is kept as a result.

Construction phase starts with an initial candidate list. The initial solution is built by adding elements from restrictive candidate list (RCL). RCL is constructed by checking and selecting each element of the candidate list for greedy-randomized function value which depends on a parameter, [0, 1]. . = 0 provides randomness which allows selecting candidate randomly from candidate list. For = 1 construction is greedy which means best candidates are selected.

GRASP(Max_Iterations, Seed)

CliqueSize = 0;

for k= 1, â€¦â€¦.., Max_Iterations do

Compute ;

Initial_Solution = GreedyRandomizedConstruction(V ,E, Î±);

Local_Minima = LocalSearch(V ,E, Q);

if |Q| > CliqueSize do

CliqueSize = |Q|;

Q* = Q;

end if

end

return(Q)

end GRASP

Figure 3.4: Pseudo code for GRASP for maximum clique problem

At the each iteration candidate list is updated according to problem neighborhood definition. Local search explores the neighborhood of current solution to find a local minimum. The length of parameter provides algorithm greediness or randomness. Hence it is a crucial parameter as it influences RCL. We describe the GRASP for maximum clique problem. To describe GRASP, we specify a construction mechanism and local search procedure.

Figure 3.5 illustrates the construction mechanism of the GRASP for maximum clique problem. The Construction phase starts with an empty clique and builds a clique by adding vertices one by one. Let C denote the set of candidate vertices and it includes all the vertices initially, i.e. C = V. A restrictive candidate list (RCL) is constructed by adding vertices which have a high degree in the graph induced by all vertices in candidate list. High degree vertices are determined by a greedy randomized function dmin + Î± (dmax - dmin). Thus, GRASP uses vertex degrees as guide for construction of a clique.

GreedyRandomizedConstruction (V ,E, Î±, Q)

Initial clique Q = ;

Candidate list C = V ;

while |C| > 0 do

Let G(C) be the subgraph induced by the vertices in C;

Let deg G(C) (u) be the degree of u C with respect to G(C);

dmin = min{deg G(C) (u) | u C};

dmax = max{deg G(C) (u) | u C};

RCL = {u C | deg G(C) (u) â‰¥ dmin + Î± (dmax âˆ’ dmin)};

Select u at random from the RCL;

Q = Q {u};

C = NC(u);

end while;

return(Q);

end GreedyRandomizedConstruction;

Figure 3.5: Illustration of GRASP construction procedure for maximum clique problem

A vertex is a candidate to be included in the clique if it is adjacent to all vertices in a clique. One vertex from RCL is selected at random and is added to the clique under construction. After addition of a vertex, candidate list is updated, i.e. in case of a clique, the newly added vertex and all other candidate vertices not adjacent to clique under construction are eliminated from candidate list and vertices adjacent to all previously selected clique vertices are form candidate list. The construction mechanism terminates when no one vertex is found to form a candidate list, i.e. the set of candidate vertices is empty.

Local search can be implemented simply by (1, 2) swap or exchange approach. This approach seeks two vertices not in a clique to be included in the clique by removing a vertex from a current clique to increase the clique size by one. The local search terminates when no such two vertices can be found in the neighborhood of current clique by removing a vertex from current clique and return clique as a result. GRASP uses memory only for storing solutions return by local search to result a best solution by comparing solutions return by local search to previously stored best solution. Thus GRASP is more adaptive than any other metaheuristics. Additionally, because of its simplicity, it is generally very fast and able to produce good solutions in less computational time.

LocalSearch(V ,E,Q)

H = {(v, u, w) | v, u, w V, (v, u) E, w Q,

and v and u are adjacent to all vertices of Q except w};

while |H| > 0 do

Select (u, v, w) H;

Q = Q {u, v} \ {w};

H = {(v, u, w) | v, u, w V, (v, u) E, w Q,

and v and u are adjacent to all vertices of Q except w};

end while;

return Q;

end LocalSearch;

Figure 3.6: Illustration of local search procedure for maximum clique problem

In next chapter, we will study and design GRASP in context of co-k-plexes to find maximum co-k-plex in greater detail. The GRASP for finding maximum co-k-plex is similar to the GRASP for maximum clique problem.

CHAPTER FOUR

The maximum co-k-plex problem is a NP-hard problem as discussed earlier in this. Therefore, we need metaheuristic algorithms to solve such problems in relatively small amount of time to produce good solutions. We choose Greedy Randomized Adaptive Search procedures (GRASP) to solve maximum co-k-plex problem due to its simplicity and flexibility. This chapter studies GRASP metaheuristic algorithm for maximum co-k-plex problem in greater detail.

4.1 GRASP ALGORITHM FOR MAXIMUM CO-K-PLEX PROBLEM:

GRASP is an iterative metaheuristic used for combinatorial optimization problems. Local search performance is greatly depends on quality of initial solution. Thus, GRASP metaheuristic is designed to construct quality solutions to enhance performance of local search. It is a first metaheuristic which emphasizes on construction of initial solution. An iteration of the GRASP consists two phases: greedy randomized construction phase and a local search.

GRASP(Max_Iterations, Seed)

Co-k-plexSize = 0;

For k= 1, â€¦â€¦.., Max_Iterations do

Compute Î±;

Initial_Solution = GreedyRandomizedConstruction(V ,E, Î±);

Local_Minima = LocalSearch();

if || > Co-k-plexSize do

Co-k-plexSize = ||;

* = ;

end if

end

return();

end GRASP

Figure 4.1: Illustration of GRASP for maximum co-k-plex problem

4.1.1 CONSTRUCTION PHASE:

Construction phase is started with an empty solution and stopped when a feasible solution is constructed in the successive iterations. During the iteration the choice of the next element to be added is greedily determined by sorting all the candidate elements in the candidate list C. The list of the best candidates is constructed by randomly choosing all best feasible candidates from candidate list which can be inserted into the partial solution under construction without destroying feasibility and whose quality is superior to the threshold value [14]. Such a list called as restricted candidate list (RCL) and it can be limited either by cardinality or value. RCL is associated with a threshold parameter Î± Ð„ [0,1]. A value Î± = 0 corresponds to a pure greedy algorithm, while Î± = 1 is equivalent to a random construction. Threshold parameter, Î± (alpha) controls the amount of greediness and randomness in the algorithm.

In our algorithm, Restrictive Candidate List (RCL) is limited to cardinality of the node (degree of the node with respective to the candidates in the candidate list). Restrictive candidate list contains best candidates choose from candidate list by greedy randomized function which is as follows:

dG(C) (u) [ d min + Î± (d max - d min )]

where,

dG(C) (u) be the degree of a candidate in subgraph induced by vertices in C.

d min be the minimum degree among degrees of candidate in candidate list.

d max be the minimum degree among degrees of candidate in candidate list.

GreedyRandomizedConstruction (V ,E, Î±, Q)

Initial co-k-plex, = ;

Candidate list C = V;

while |C| > 0 do

Let G(C) be the subgraph induced by the vertices in C;

Let deg G(C) (u) be the degree of u C with respect to G(C);

d min = min{dG(C) (u) | u C};

d max = max{dG(C) (u) | u C};

RCL = {u C | dG(C) (u) d min + Î± (d max âˆ’ d min)};

Select u at random from the RCL;

= {u};

C = NC(u),such that dG(C) (u) k-1;

end while;

return();

end GreedyRandomizedConstruction;

Figure 4.2: Pseudo code for Construction phase

Best candidates from RCL are randomly selected to add in partial constructed solution. Finally, candidate list is updated as the selected element is incorporated to the partial solution. We simply track degrees of the unexplored nodes to update candidate list without violating the feasibility.

4.1.2 LOCAL SEARCH PHASE:

The local search is usually used to improve the constructed solution because the solutions built by a greedy randomized construction phase are not necessarily optimal, even with respect to simple neighborhoods. Local search is started with a greedy randomized initial feasible solution constructed in the construction phase. In the local search neighborhood of the feasible solution is investigated and current solution is replaced by better solution in successive iterations if algorithm encounters such solution. Local search terminates when no better solution is found in the neighborhood of feasible solution and returns the local optimum solution. Figure 4.3 illustrates the pseudo code for Local search phase.

LocalSearch(V ,E, )

H = {(v, u, w) | v, u, w V, (v, u) E, w ,

and v and u such that adding them to , will remain a co-k-plex};

while |H| > 0 do

Select (u, v, w) H;

= {u, v} \ {w};

H = {(v, u, w) | v, u, w V, (v, u) E, w ,

and v and u such that adding them to , will remain a co-k-plex};

end while;

return ;

end LocalSearch;

Figure 4.3: Local search for maximum co-k-plex problem

Local search can be opted by adding good candidates to current solution and removing bad candidates from current solution. Such procedure is called as "swapping" or "exchange" candidates. Usually (1, 2) (removing 1 and adding 2) swap or exchange is opted to find better solution in the neighborhood of the current solution. The neighborhood for our problem is defined as follows;

Definition 4.1: Given a (maximal) co-k-plex () , The local search neighborhood as,

Nq() = { J V | J is a co-k-plex and

| \ J | = 1 and

| J \ | = q}

i.e . (1,q) exchange neighborhood for prespecified q = 2, 3, 4â€¦

The neighborhood search can be implemented by using either a best-improving or first improving strategy. In best-improving strategy, all neighbors of the current solution are invstigated and evaluated for best improving neighbor. But first improving strategy uses first improving neighbor as it encounters. Firt improving strategy is used when far amaller computational time. We use first improving strategy to reduce the running time of algorithm. For exploring neighborhood of maximal co-k-plex, algorithm uses (1,q) swap. First algorithm iteratively searches for the two candidates in the neighborhood of current solution by eleminating one candidate from it and Then algorithm searches for distinct q vertices which can be added directly to the current co-k-plex to improve it. Local search terminates when no two vertices are found to improve current solution and return the current solution as local minimum. Figure 4.4 illustrates (1,q) exchange in local search.

Let k = 2, then the maximum degree of a node in a co-k-plex less than or equal to k-1 i.e. 1. Suppose construction phase built a co-k-plex set {1-2}i.e.Local search starting solution is

{1-2}. In this graph Local search finds two distinct node 3 and 4 by eleminating node 2 from the current solution. Now current solution becomes {1-3-4} but it is not optimal because nodes 5 and 6 can be added to current solution to form maximum co-k-plex i.e.{1-3-4-5-6}. So we can add four nodes by eliminating node 2 which is simple a (1,4) exchange where q = 4.

Figure 4.4: illustration of (1,q) exchange in local search

Therefore, effectiveness of the local search depends upon various factors such as quality of initial or starting solution built in construction phase, Neighborhood structure and the neighborhood search techniques etc. therefore, The construction phase plays a very important role with respect to building high-quality starting solutions.

CHAPTER FIVE

This topic represents research activities to be carried out for successful completion of this thesis.

5.1 RESEARCH ACTIVITIES:

The overall aim of this thesis work is to design and develop GRASP metaheuristic algorithm to solve "maximum co-k-plex problem". Specific tasks are planned as listed below,

To perform thorough literature survey available on underlying research problem

To perform thorough literature survey on metaheuristics used to solve large combinatorial optimization problems.

To develop Greedy Randomized Adaptive search Procedure (GRASP) metaheuristic algorithm to solve underlying research problem.

To implement and conduct a detailed computational study on GRASP metaheuristic algorithm for maximum co-k-plex problem.

5.2 FUTURE WORK:

Hybridize GRASP and Path-relinking metaheuristics to intensify GRASP search procedure (intensification procedure for GRASP).

Study stock market graphs and apply algorithm to stock market graphs.