Lattice diagrams, known as Hasse diagrams, have played an ever increasing role in lattice theory and fields that use lattices as a tool. Initially regarded with suspicion, they now play an important role in both pure lattice theory and in data representation. Using evolutionary algorithms-genetic algorithms for drawing a lattice diagram is the main goal of our research. It depends on stochastic methods on searching of concepts' positions, with trying to draw it with less number of intersections.
Known approaches of lattice drawing By the 1970s diagrams had become an important tool in lattice theory. There exist some known methods how to draw the Hasse diagrams. The first one it called Hierarchical Layout Partially ordered sets, for the purposes of layout, are seen as hierarchies. An annotated bibliography by Battista et. [1] describes the approach as
A hierarchical drawing of an acyclic diagram is an upwards polyline drawing where the vertices
and bends are constrained to lie on a set of equally spaced
horizontal lines.
Sugiyamas algorithm is typical of a variety of algorithms proposed for the layout of such diagrams. There are three main steps of whole process. 1. Partition the vertices into layers. 2. Reduce the number of edge crossings by swapping the horizontal ordering of vertices. 3. Minimize the number of bends, where bends are dummy nodes inserted to ensure that lines travel only between adjacent layers.
Next there are additive or non additive diagrams and the methods to draw Hasse diagrams which were introduced by Rudolf Willw [11]. But we can mention the main points of each drawing.
These are the most important points to draw a readable graph: – Avoid crossing of lines. – Try to draw parallel lines. – Identify known structures: cubes, rectangles . . . – Layer the nodes: draw nodes on the same layer, if their concept’s extents have the same size.
– Try to draw steep lines, avoid aflt ones. 2
Evolutionary Algorithms Evolutionary algorithms are stochastic search methods that mimic the metaphor of natural biological evolution, which applies the principles of evolution found in nature to the problem of finding an optimal solution to a solver problem. An evolutionary algorithm is a generic term used to indicate any population-based optimization algorithm that uses mechanisms inspired by biological evolution, such as reproduction, mutation and recombination. Candidate solutions to the optimization problem play the role of individuals in a population, and the cost function determines the environment within which the solutions ”live” (see figure 1. Evolutionary Algorithms
Evolutionary algorithms are stochastic search methods that mimic the metaphor of natural biological evolution, which applies the principles of evolution found in nature to 84 thSeuphroabillemOowfafiinsd,inPgeatnr oGptaimjdalsos,ˇoVlaut´ciolanvtoSansaseˇo´llver problem.
An evolutionary algorithm is a generic term used to indicate any population-based optimization algorithm that uses mechanisms inspired by biological evolution, such as 1). Evorleuprtoidounctioonf, tmhuetaptioonp uanldatrieocnomtbhineantiont.akCeasndpidlaatecesoalufttioenrs tthoethreepopetaimtiezdatioanpplication problem play the role of individuals in a population, and the cost function determines the of the eanbvoirvonemoenpt ewriathtinorwsh.icFhtihgeusroelut1ionssh"loivwe"s [1t]h.eEvsotlurtuiocntouf rthee opofpualatsiiomntphelne taekveoslutionary algorithpmlacefoafrtersothlevrienpgeataedparpoplbiclaetimon.oGfteheneabtoicveaolpgeorartoitrsh. mFiguisre t1hsehomwsotshte sptroupctuurlear type of of a simple evolutionary algorithm for solving a problem. Genetic algorithm is the most evolutioponpaurlayr type of evolutiso.nary algorithms.
algorithm
Coding of solutions Objective function Evolutionary operators fitness assignment mutation selection Recombination Evolutionary
Search
Fig. 1. Basic scheme of our solution. 2. Genetic Algorithms (GA)
Genetic algorithms (GA) described by John Holland in 1960s and further 3 Gtdeheenve1el9o6pt0eidscabnyAdH1ol9lg7la0onsdr[2ain]t.dhGhAimsustssuedde(nDGtsarawAnidn)icaonllEeavgouluetsioant tthoeeUxtnraivcetrnsiattyuroef oMpitcimhiigzaantioinn strategies that use them successfully and transform them for application in mathematical Geneticopatilmgiozartiitohnmthesor(y GtoAfin)ddtheesgclroibbaleodptbimyumJoinhdnefHineodllpahnasdesipnace19[36, 04,s5a].nd further developed by HollGaAndisaunsdedhtios esxtturadcte naptpsroaxnimdatceosloleluatigounsesfoar tptrohbelemUsntihvreorugshitya oseft Mofichigan in the 196po0prisenrcaaitpniolednss 1o“f9fi7ten0veossls.utGfiuonnAcatriyounsb, eiosdleolegDcytaioarnpw,plciienrodisastonovecEro,mvaopnuldutetmriuostcnaiteinotcnoe”..eGSxuAtcrhasecoatprcenhraatpotrruoscreaesresoptimization strategies that use them successfully and transform them for application in mathematical optimization theory to find the global optimum in denfied phase space [4][5][6].
GA is used to extract approximate solutions for problems through a set of operations ”tfiness function, selection, crossover, and mutation”. Such operators are principles of evolutionary biology applied to computer science. GA search process depends on different mechanisms such as adaptive methods, stochastic search methods, and use probability for search.
Using GA for solving most difficult problems that searches for accepted solution; where this solution may not be the best and the optimal one for the problem. GA are useful for solving real and difficult problems, adaptive and optimization problems, and for modeling the natural system that inspired design [9][2].
Some applications that can be solved by GA are: Scheduling ’Job, and Transportation Scheduling’, Design ’Communication Network design’, Control ’Gas pipeline control’, Machine Learning ’Designing Neural Networks’, Robotics ’Path planning’, Combinatorial Optimization ’TSP, Graph Bisection, and Routing’, Signal Processing ’Filter Design’, Image Processing ’Pattern recognition’, Business ’Evaluating credit risks’, and in Medical ’Studying health risks for a population exposed to toxins’ [10].
Genetic Algorithms Operators 1. Chromosome or individual representation. 2. Objective function “tfiness function”. 3. Genetic operators (selection, crossover and mutation).
Where applying GA done over a population of individuals or chromosomes shows that several operators are utilized. Presenting of GA process described in a flowchart shown in 2. 4.1 Encoding by simple; representation of integer numbers by binary encoding. Representation for chromosome (suggested solution) will be in a string of symbols to simplify using of GA operators and to help in reproduction of optimal solution. Encoding may be in string of bits, or in arrays, or in lists, or in tree structure, and may be in other types. Some examples were shown in table 1. Selection determines which solution candidates are allowed to participate in crossover and undergo possible mutation. Select two chromosomes with the highest quality values from the population using one of the selection methods. Some of these methods are: Elitism Selection, Roulette Wheel Selection, Tournament Selection, Rank Selection, and Stochastic Selection. 4.4
Crossover operator Promising candidates, as represented by relatively better performing solutions, are combined through a process of binary recombination referred to as crossover. This ensures that the search process is not random but rather that it is consciously directed into promising regions of the solution space. Crossover exchanges subparts of the selected chromosomes, where the position of the subparts selected randomly to produce offsprings. Some of crossover methods types are: Single Point Crossover, Two Points Crossover, Multipoint Crossover, Uniform Crossover, and Arithmetic Crossover. 4.5
Mutation operator New genetic material can be introduced into the population through mutation. This increases the diversity in the population. Mutation occurs by randomly selecting particular elements in a particular offsprings.
GA process terminated by satisefis one of terminating conditions often include: – Fixed number of generations reached. – Budgeting: allocated computation time/money used up. – An individual is found that satisfies minimum criteria. – The highest ranking individual’s tfiness is reaching or has reached a plateau such that successive iterations are not producing better results anymore. – Manual inspection. May require start-and-stop ability.
– Combinations of the above. 5
Genetic algorithm implementation In the this chapter we try to describe our approach to draw a Hasse diagram for a concept lattice using genetic algorithm. There are five levels and ten concepts (nodes) in the figure 3. In the rfist generation the population of a chromosomes were generated randomly. At the beginning the number of levels is computed according to an incremental algorithm made by Petko Valtchev. Then we compute the level position for each node, some nodes may appear in different levels, e.g. the concept number six could be moved one level up. Next vector (see table 2) consists of all edges in the Hasse diagram. The numbers represent the indexes of nodes (concepts).
From To 0 0 0 5 5 8 8 6 6 9 9 7 4 2 6 5 9 3 4 3 9 4 2 7 2 1 1 1
Table 2. Vector of diagram edges
Fig. 2. asdadadad 2 9 8 6 7 1 0 3 5 4 eLvl 4 eLvl 3 eLvl 2 eLvl 1 eLvl 0 5.1 Chromosome encoding Each chromosome was encoded as a vector which consists of x and y coordinates for all nodes in the graph. The coordinates will be generated randomly for node with respect to the levels of nodes. Table 3 shows an example for such chromosome. We are looking for more readable graph. The most important constrains we look for the minimal number of edges’ intersections. 6.1
Selection method The best two chromosomes will be selected depends on the minimal number of intersections and called parents. They will be used in the other operators crossover and mutation to produce two new offspring. 6.2
Crossover three types.
Three types of crossover will be implemented (single point, two points and multi points crossover) over selected parents. Following figures show examples for the
For the single point crossover (see gfiure 4) the one node position will be randomly chosen. It will divide the parents’ chromosomes into two parts. Then first offspring’s chromosome consists of the rfist part from the first parent and second part from the second parent. The second offspring consists of the rfist part from the second parent and the second part from the first parent. sfpring aPrent 1
Y
02 03 03
03 05 04 01 02 01
02 04 02 01 05 520 07 520 03
02 02 X fO sfpring 2 aPrent 2 fO sfpring
1 02 03 03
03 05 04 01 01 01
02 Y 05 520 07
520 02 02 05 02 01
07 X
04 02 01 03
02 03 520 720
810 02 X
02 Y 03 01
01 05 04 03 03 01
02 05 04 03 03 01
02 Y 02 03 01 02 03 02 02 05 520 720 810 02 01
07
X aPrent 1
Y
02 05 04 03 03 01 02 03 01
02 9 aPrent 0
SX u a g r a p h s y m m e t r y o r m i n i m a l s u m o f l e n g t h s o f g r a p h e d g e s .
B u t t h i s i s t h e p o i n t o f c o n c r e t e i m p l e m e n t a t i o n
. 6 . 4
T e r m i n a t i o n p r o c e s s T h e p r o c e s s w i l l b e t e r m i n a t e d i f a n y o f t h e s e c a s e s : 1 .
t h e r e w i l l b e a c h r o m o s o m e w i t h n o i n t e r s e c t i o n w h i c h m e a n s t h e b e s t s o l u t i o n
, 2 .
a f t e r p r o c e s s i n g l i m i t e d n u m b e r o f g e n e r a t i o n s .
i f t h e r e i s n o i m p r o v e m e n t o v e r t h e p o p u l a t i o n i n l i m i t e d n u m b e r o f g e n e r a t i o n s . The genetic algorithms are used to solve hard problems, where the drawing of a nice and readable Hasse diagram is one of them. We introduced one possible way to draw it using genetic algorithm. Using different types of the crossover operators may produce god drawing results. Moving nodes from level to level by mutation operator may give us better results.
In our future work we will try to create an application for lattice drawing based on our approach. The shape of the graph could be improved using other characteristics like distances between nodes on the same level. 1. G. Battista, P. Eades, R. Tamassia, and I. Tollis. Algorithms for drawing graphs, an annotated bibiliography. Computational Geometry, Theory and Applications, 4:235–282, 1994. 2. H. Fang, P. Ross, and D. Corne. Genetic algorithms for timetabling and scheduling.
http://www.asap.cs.nott.ac.uk/ASAP/ttg/resources.html, 1994. 3. B. Ganter and R. Wille. Formal Concept Analysis. Springer-Verlag Berlin Heidelberg, 1999. 4. D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989. 5. M. Melanie. An Introduction to Genetic Algorithms. A Bradford Book. MIT-Press, 1999. 6. M. Melanie and S. F. Genetic algorithms and artificial life. Santa Fe Institute, working Paper 93-11-072, 1994. 7. S. S. J. Owais. Timetabling of lectures in the information technology college at al al-bayt university using genetic algorithms. Master’s thesis, Al al-Bayt University, Jordan, 2003. in Arabic. 8. H. Pohlheim. Evolutionary algorithms: Overview, methods and operators.
GEATbx version 3.5., 2004. http://www.geatbx.com/docu/index.html. 9. E. P. K. Tsang and T. Warwick. Applying genetic algorithms to constraints satisfaction optimization problems. In Proc. Of 9th European Conf. on AI. Aiello L.C., 1990. 10. R. L. Wainwright. Introduction to genetic algorithms theory and applications. The
Seventh Oklahoma Symposium on Artificial Intelligence, November 1993. 11. R. Wille. Lattices in data analysis: How to draw them with a computer. Algorithms and Order, pages 33–58, 1989.