30-07-2012, 01:28 PM
Breaking the Symmetry of the Graph Colouring Problem with
Genetic Algorithms
ABSTRACT:
Genetic Algorithms have so many applications and can be applied in so many fields.There are so many methods of graph coloring like Bell-man ford method,Back tracking method ,but in case of large graphs-a graph contain so many vertices and edges ,these methods do not give good results. Genetic Alorithms that based on recombination applied here but due to recombination sometimes they generate poor offsprings resulting symmetries that also not suitable.So here I am trying to generate a modified version of genetic Algorithm that will remove symmetries in graph and also reduce number of bad edges.
INTRODUCTION:
Graph Coloring idea have been proposed in several papers.The approach followed is generally minimum number of colors is used to color the vertices or edges of graph in such a way that no two adjacent vertices have same color .V indicate set of vertices and K indicate set of colors.Minimun number of k from the set K indicate good solution.If two adjacent vertices have same color then the edge connecting the vertices known as bad edge.Genetic Algorithm is used here to color the vertices of the graph ,it is based on recombinations and generations ;so to find a new generation-recombination takes place.In case of recombination the chances of bad edges is increased and the offsprings go worst than that of parents.
If we fixed the nodes by deciding number and their position then the chances of bad edges and symmetries will reduced.Previously the solutions we obtained, provide symmetric results for ex: the sequence 111234 and 444231 are symmetric .Now by the new approach the results may same and repeated but not symmetric.The vertex graph colouring problem (VGCP) consists of finding a partition ofthe graph G into K color classes such that the number of edges with both endpoints in the same class is minimised. We will refer to such edges as bad as defined earlier. The smallest value of k for which G has no bad edges is called the chromatic number of the graph.The VGCP is known as NP-completed and its some features can be investigated according to grover(1992) while Cheeseman ,Kenefsky and Taylor found that it is possible to measure the hardness of the problem.
PROBLEM DOMAIN:
Graph can be colored by using one of the standard methods .Heuristics approach given by Welsh ,Dsatur are generally used to color the graph.Graph coloring are generally helpfull in solving scheduling problems like a college timetable.Here the domain is to break the symmetry of the graph coloring so When Genetic algorithm is applied on the graph ,offsprings generated and give worst results i.e the number of the bad edges are increased as compared to the parent generation .So the aim is remove the symmetry occur in solution space and to reduce the number of bad edges which is known as cost . New algorithms are designed by modifying the operators of standard Genetic Algorithm according to the graph used.There are some standard graphs are taken and the new genetic algorithms are applied on these graphs and results are shown.
SOLUTION DOMAIN:
The standard genetic algorithm was not suitable for the purpose.Genetic algorithm has two main operators crossover and mutation ,so when these operators are applied to solve the problem , instead of optimized solution we get harsh results means offsprings generated and give worst results i.e the number of the bad edges are increased as compared to the parent generation .So the aim is remove the symmetry occur in solution space and to reduce the number of bad edges which is known as cost .
Method-identify a clique of size at most K(set of colors).
-All nodes are then assigned different colors and marked to aviod furteer modifications.
-Mutations and crossover apply to all vertices of the graph but those marked .
-Typical mutation opreator is replaced by a greedy selection that reduces the cost of whole solution .
1.Find good approximations for general graph while keeping the alge as simple as possible.
2.The evolutionary process terminates either generations exceeds 10,000 or cost is 0.
3.A genetic approach with greedy mutation is used for those graph where partition of graph takes place.
4.Swap mutation and 1 point crossover is also used for some graphs for optimized solutions.
5.Cyclic permutation is also used in some other standard graphs.
SYSTEM DOMAIN:
Genetic Algorithm can be implemented in C , C++ , Java and MATLAB.In C , C++ and java implementation is difficult because developer has to designed new methods and function according to the algorithm from the initial level while in MATLAB readymade tools are present and also the graphical view is very good to judge the result .So MATLAB is the most preferable technology .
Platform-Windows xp and further version.
RAM-1 GB
HARD DISK-50 GB
No special technology and environment is required for the genetic algorithm.But as we increase the specification the speed of algorithm is increased that increases the performance.
APPLICATION DOMAIN:
Genetic Algorithms are applied in many fields like Automotive Design,Engineering Design ,Robotics , Telecommunication Routing ,Trip, Traffic and Shipment Routing , computer gaming ,encryption code breaking etc.The Genetic algorithm implemented here is specially for graph coloring which can easily solve the problems of scheduling like time table problem.
Detail:-Suppose we have teachers, classes and lectures ,now the task is assign the teachers classes and lectures in such a way class and lecture will not clash i.e. a unique solution should be there for every teacher because at a time a single teacher cannot be present in two classes /lectures or a class cannot be assigned to two lectures altogether.
EXPECTED OUTCOME:
If the idea that I thought is successful than the symmetries generated after recombination may be removed also the number of bad edges is reduced and the optimized result can be seen .In case of standard GA approximately thousands or above iterations are done that takes a lot of time and also in some cases after these iterations result is nor produced and we find a high cost that is not suitable.If the operators are modified than we see better results for different types of graphs.