Solving N Queens Problem Using Genetic Algorithms

6194 words - 25 pages

1 IntroductionThe N-Queens problem is a classical AI problem. Its name is derived from the allowed moves for the queen piece in chess. Queens are allowed to move horizontally, vertically, or diagonally, backward and forward, with the only restriction being that they can move in only one direction at a time. A queen that can reach another piece in one move captures it.The N-Queens problem is based on the notion of trying to place N queens on an N x N grid, such that no queen will be able to capture any other queen. The N-queens problem is typical of many combinatorial problems, in that it is simple to state and relatively easy to solve for small N, but becomes difficult with a large N. There ...view middle of the document...

A whole new population of possible solutions is thus produced by selecting the best individuals from the current "generation", and mating them to produce a new set of individuals. This new generation contains a higher proportion of the characteristics possessed by the good members of the previous generation. In this way, over many generations, good characteristics are spread throughout the population, being mixed and exchanged with other good characteristics as they go. By favouring the mating of the more fit individuals, the most promising areas of the search space are explored. If the genetic algorithm has been designed well, the population will converge to an optimal solution to the problem.The power of genetic algorithms come from the fact that the technique is robust, and can deal successfully with a wide range of problem areas, including those which are difficult for other methods to solve. Genetic algorithms are not guaranteed to find the global optimum solution to a problem, but they are generally good at finding "acceptably good" solutions to problems "acceptably quick". Where specialized techniques exist for solving particular problems, they are likely to out-perform genetic algorithms in both speed and accuracy of the final result. The main ground for genetic algorithms, then, is in difficult areas where no such techniques exist. Even where existing techniques work well, improvements have been made by hybridizing them with a genetic algorithm.Before a genetic algorithm can be run, a suitable representation for the problem must be devised. A fitness function also required to assign a figure of merit to each coded solution. As a summary, the procedures of genetic algorithms are as below:1. generate initial population2. compute fitness of each individual3. select individuals for mating4. mate individuals to produce offspring5. mutate offspring6. insert offspring into population7. if stopping criteria satisfied, go to "8", else go to "3"8. finishFigure 1: The procedures of genetic algorithms2 Implementation Decisions2.1 Genetic AlgorithmFirst of all, we need to choose a genetic algorithm from GAlib package. There are four kinds of genetic algorithm available. They are GADemeGA, GAIncrementalGA, GASimpleGA and GASteadyStateGA. It is alright to choose anyone of them. To make things simple, GASimpleGA was chosen.2.2 RepresentationAfter that, we need to define a representation for the N-queens problem. There are two ways to do that. The usual way is to represent it as a 2-dimensional binary array as shown at figure 2b. We are sure that no 2 queens will be in the same row and no 2 queens in the same column. So, for optimal solution, we can just represent the chessboard as a 1-dimensional integer array as shown at figure 2c. The number "X" in the array will represent there is a queen at row "X".For 2-dimensional binary array chessboard, there are in total (NxN)!/(N!x(N(N-1))!) = 64! / (8!56!) = 4426165368 permutations. However, for a...

Other Essays On Solving N-Queens Problem Using Genetic Algorithms

The Bio-Psychological Approaches To Understanding Mental Events And Behaviour Result In More Conclusive Findings Than Using A Social Approach And/Or Examining Environmental Factors. Discuss

2275 words - 10 pages -psychological approaches to understanding mental events and behaviour result in more conclusive findings than using a social approach and/or examining environmental factors. Recordings from a genetic or biological approach enables theories to be clearly proved or disproved. However, when adopting an environmental approach, ideas are often very abstract and merely symbolic. Social factors are also not as reliable, as they can suffer from possible

Consistent Perseverance Essay

615 words - 3 pages me into a journey of fairness, consideration, and sensitivity. They also provided me with the time to share my visions and goals, and time for problem solving in which members worked together to brainstorm in order to find a solution to a problem, in a process of crisis management and damage control. Last but not least, status reinforcement and emotional support were core functions of these meetings. Meeting with the club president and advisors

Study Skills "20 Questions And Answers"

1030 words - 5 pages problem solving? Describe each.Step 1: Specify the Problem. State the problem, Specify the problem in a way that allows you to solve it successfully, Express the problem verbally or in writing, Focus on language.Step 2: Analyze the Problem. Seek other perspectives, Be flexible in your analysis, Consider various strands of impact, Brainstorm about all possibilities and implications, Research problems for which you lack complete information.Step 3

Attention Deficit Hyperactivity Disorder

6461 words - 26 pages , children with ADHD show less knowledge about social behaviors and social problem-solving skills (Dumas, 1998).Concerning adolescents with ADHD, some of the symptoms of ADHD displayed in childhood may remain, others may decrease, and new symptoms may occur. It has been found that adolescents with ADHD are less socially competent and spend more time alone or with younger children than those adolescents without ADHD. It has been studied that the

Ikea.Com (Overview On The Company)

7745 words - 31 pages positions in certain key areas. These departments are "IKEA IT", "IKEA Food Services", "IKEA Indirect Materials & Services", "IKEA Raw Material", "IKEA Communications", "Module Services" and "IKEA Family Services".Value shopA value shop focuses on customer problem-solving. In a value shop the services aren't standardized, meaning that the value creation can demand different levels of intensity. The advantage in a value shop instead of a

Wood Stock 1969

1927 words - 8 pages Pop festival, which drew 40,000 people. At 24 he was the manger of a rock group called Train, he wanted to sign a record deal with. In Decemeber1968, he bought his proposal to Artie Kornfeld ant the Capital Records.Michael and Artie both lived in Bensonhurst, Queens. Michael got a appointment by telling the record company's receptionist that he was "from the neighborhood." The two guys hit it off immediately. Michael moved in with Lang and

Origins Of Psychology And Research Methods Worksheet

1550 words - 7 pages gathered, encoded and stored. Some of the concepts that are studied under cognitive psychology are perception, memory, imagery, concept formation, problem solving, reasoning, decision making, and language. Not only that, cognitive psychologists explain that a human mind works like a computer that sequentially takes in information(gathers), processes it( encodes), and then produces a response, hence called the information-processing

Case Study Essay - Stem cell Research : Students were asked to read and respond to a controversial issue raised by advances in modern biological sciences

555 words - 3 pages honestly, if we ever do allow that kind of research, we will save millions of lives. Not to mention putting the whole pharmaceutical industry out of business, because of all the newly developed treatments we will be discovering. I can keep going on about the facts that stem cell research is in-fact important to the U.S citizens, and can help in many ways.The problem is that current stocks of stem cells have taken up a "non-human molecule" called N

Phosphorylation In Yeast

2315 words - 10 pages widespread and has, or is conjectured to have a biological significance. Within a sequence or database of sequences, researchers search and find motifs using computer-based techniques of sequence analysis, such as BLAST. Bioinformatics field tends to use such techniques. The new technology in market these days is the protein-chip technology which allows thorough analysis of biochemical activities and can be used to analyze protein kinases as

Dialogue: Night on the town

434 words - 2 pages ;re way to drunk like the rest of us!J: What!E: I’m not getting in with you behind the wheel.R: Don’t be a closer Erin, get in the car, we’re leaving* Martha tries to put the key in the ignition *J: I can’t get the keys to work. It’s a sign. Let’s just take a cab. I guess I can pick up my sexy car tomorrow.E: Okay! Great! I’ll call the cab.R: Fine, but I’m not paying!N: In the wise words of Aristotle, the only difference between beasts and a human is reasoning. Although they drank like beats, they proved they were human by using their reasoning when deciding whether or not to drive under the influence.

Thermodynamics Paper

522 words - 3 pages relationships between the variables, and the multiple definitions of energy greatly simplify problem solving throughout all of thermodynamics.We can form the Partition Function as a measure of the total weighted probabilities of the various states of a system, and relate this quantum counting result to the energy of a the system. The spectrum of blackbody radiation is derived directly from this counting. For systems in thermal and diffusive contact with a

Similar Papers

Biomedical Technology Essay

1009 words - 5 pages , selectively promoting the growth of the best cells for the task, "fine tuning his circuits." Sponsored by the U.S.DARPA, he is devising a group of cells called "algorithms," which allow bacteria to figure out how far away a stimulus is and very reactions accordingly (Gravitz).Thomas Tuschi has an off switch for genetic diseases. In Germany's May Planck Institute for Biophysical Chemistry, he discovered that double stranded RNA if designed to target a

Coding Theory Essay

1832 words - 8 pages strings differ, that is, the number of i (i = 1, 2 . . . , n) for which xi ≠ yi" (Rosen, 1999).The smallest Hamming Distance among all possible data words in a set is called the Minimum Hamming Distance. In a coding scheme, is used to define the Minimum Hamming Distance.Linear CodesLinear codes are more efficient than other codes for encoding and decoding algorithms. Linear codes are special sets of words of length n over an alphabet {0,..,q -1

Human Cloning Should Not Be Banned

3678 words - 15 pages and that they will grow up to be just like their donors. This is where many people are wrong.� Nature has been producing clones for millions of years through the process of identical twins. Identical twins have the same genetic makeup of each other, yet develop into separate individuals with distinct personalities (Cole). This shows that genetic makeup does not play a big role in our individuality, but that our individuality comes from our

Goals Planning Essay

5604 words - 23 pages ' needs and rebalances the portfolio from time to time in view of changing market conditions requires extensive problem solving and decision making skills. Communications and relationship management skills help to foster long lasting relationships with clients. Having initiative and a good global mindset can be a competitive advantage to managing clients' fund. (Workforce Development Agency 2008)Using framework from the Financial Industry Competency