Explain how your genetic algorithm works

Assignment Help Data Structure & Algorithms
Reference no: EM131860843

Assignment: Search

This assignment will require you to explore a variety of search techniques on two problems.

Part 1 - Heavy N-queens problem

The problem -

For this problem, you will work on a variant of the N-queens problem we discussed in class. The queen pieces are very heavy, and therefore difficult to move. The cost to move a queen is 10 plus the square of the number of tiles you move it. So to move a queen upwards 4 squares in a column costs 10 + 42 = 26. Otherwise, the rules are identical to the N-queens problem.

Approaches

You will use two approaches for this problem: A* and greedy hill climbing with restarts. For A*, you need a heuristic function. The number of (directly and indirectly) attacking queens is a good place to start. Since moving a queen costs 10 points, you can modify the heuristic to be:

1. If no attacking queens: 0

2. If attacking queens: 10 + # of pairs of attacked queens

Note: it is not immediately clear if this heuristic is admissible. Moving one queen can reduce the cost dramatically (as we talked about in class). However, given the fixed cost of 10 to move a queen, perhaps no situation arises where the true cost is less than the heuristic value. For extra credit, prove either that the heuristic is admissible or produce a counterexample to demonstrate that it is not.

For hill climbing with restarts, you should use the same heuristic function as for A* and perform greedy hill climbing. If you have not found a solution, and fewer than 10 seconds have elapsed since the program started running, you should do another iteration of hill climbing with a random start state.

Program behavior -

Your program should take as input the N value for the N-queens problem and the type of search to conduct (1 for A*, 2 for greedy hill climbing). For example, passing in a "30" results in a 30-queens puzzle. You can take input as command-line input, or read it from a file if command-line input is difficult for the language you are using. Just explain how in your writeup.

Your program should output:

The start state (a simple text representation is fine)

The number of nodes expanded. Consider an expansion as when you visit a node and compute the cost for all of the possible next moves. For hill climbing, remember to count this value across all of the restarts!

Time to solve the puzzle

The effective branching factor: consider how many nodes were expanded vs. the length of the solution path

The cost to solve the puzzle. Note that A* computes cost automatically, but you will but tneed to extend greedy search to keep track of this number. Note that cost does not include any failed runs with greedy search -- just compute the cost of the path it computes for the board it solves. (Note the comparison with A* is not quite fair since greedy search gets to discard its results from tougher boards)

The sequence of moves needed to solve the puzzle, if any (hill climbing may fail).

Write-up -

You should conduct experiments to determine:

1. How large of a puzzle can your program typically solve within 10 seconds using A*? Using greedy hill climbing?

2. What is the effective branching factor of each approach? For this computation, perform 10 runs of a puzzle half the maximum size you calculated for step #1.

3. Which approach comes up with cheaper solution paths? Why?

4. Which approach typically takes less time?

Part 2 - Urban planning

The problem -

For this problem, you will use hill climbing and genetic algorithms to determine the ideal location of industry, commerce, and residential sections a city. You will input a map with the following symbols:

  • X: former toxic waste site. Industrial zones within 2 tiles take a penalty of -10. Commercial and residential zones within 2 tiles take a penalty of -20. You cannot build directly on a toxic waste site.
  • S: scenic view. Residential zones within 2 tiles gain a bonus of 10 points. If you wish, you can build on a scenic site but it destroys the view.
  • 0...9: how difficult it is to build on that square. You will receive a penalty of that many points to put anything on that square.

You will have to place industrial, residential, and commercial tiles on the terrain.

  • Industrial tiles benefit from being near other industry. For each industrial tile within 2, there is a bonus of 3 points.
  • Commercial sites benefit from being near residential tiles. For each residential tile within 3 squares, there is a bonus of 5 points. However, commercial sites do not like competition. For each commercial site with 2 squares, there is a penalty of 5 points.
  • Residential sites do not like being near industrial sites. For each industrial site within 3 squares there is a penalty of 5 points. However, for each commercial site with 3 squares there is a bonus of 5 points.

Note that all distances uses the Manhattan distance approach. So distance is computed in terms of moves left/right and up/down, not diagonal movement.

Approaches -

You will use hill climbing with restarts and genetic algorithms for this assignment. When your hill climbing restarts, it may not ?modify the map! It can only change where it initially places the different zones to begin the hill climbing process.

Your genetic algorithms will have to come up with a representation, selection and crossover methods, and must make use of culling, elitism, and mutation.

Program behavior -

Your program will read in a file where the first 3 lines are the number of industrial, commercial, and residential locations (respectively). The remainder of the file is a rectangular map of the terrain to place the town. Your program should then run for approximately 10 seconds and output the following to a file:

  • The score for this map
  • At what time that score was first achieved.
  • The map, with the various industrial, commercial, and residential sites marked.

Write-up -

You should analyze your program's behavior to answer the following questions:

1. Explain how your genetic algorithm works. You must describe your selection, crossover, elitism, culling, and mutation approaches.

2. Create a graph of program performance vs. time. Run your program 10 times and plot how well hill climbing and genetic algorithms perform after 0.1, 0.25, 0.5, 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 seconds. If you only had 0.25 seconds to make a decision, which technique would you use? Does your answer change if you have 10 seconds?

3. How do elitism and culling affect performance?

4. How did you perform selection and crossover for your population? Find some known method for doing selection, other than the one described in class. Explain what you did.

Reference no: EM131860843

Questions Cloud

Identify the systems in the organization : Identify the systems in the organization (i.e., the type and number of computer systems and operating systems use, along with top-level view of infrastructure).
Democracy for someone who works fulltime : From GIVE ME LIBERTY, BY Eric Foner, Seagull volume 2. According to John Mitchell in the excerpt from 1910 on page 711 (page 699 in Fourth
Summarize the benefits of story telling as healing practice : Reflecting on Theresa and Sarah's Story, Have you ever held an assumptive belief about a particular group in society? Elaborate on your answer.
Radical republicans during reconstruction : Over the course of U.S. history, many groups have tried to reshape U.S. society and politics in accordance with a vision they see as the promise of America
Explain how your genetic algorithm works : CS 534 Assignment: Search. Explain how your genetic algorithm works. You must describe your selection, crossover, elitism, culling, and mutation approaches
How is replication control achieved in ddbms : How is Replication Control achieved in DDBMS?What is CAP Theorem in Distributed Systems? How is it different from ACID in Relational DBMS?
Develop an employee class that keeps data attributes : Develop an Employee class that keeps data attributes for the following pieces of information: Employee name and Employee number.
Why have some historians labeled the thirty years : Why have some historians labeled the Thirty Years' War the "last of the religious wars", while others have called it the "first modern war"?
How did the instability of politics at the turn : How did the instability of politics at the turn of the century show itself in daily life and art? How did this set the stage for the coming war?

Reviews

len1860843

2/12/2018 5:31:57 AM

What to hand in: You should submit your assignment on Canvas. Submit one file for part 1, and one file for part 2. Include instructions for how to run your code. If the TA needs help from you or is confused, you will lose points. The writeups from part 1 and 2. Hints - There is a moderate amount of analysis and writeup for this assignment -- do not forget that component. Your program should run for the specified length of time. Note the person grading your program may have a different hardware setup, so do not have a fixed number of iterations before the program terminates. Instead use calls to determine the amount of elapsed time. We are not worried about perfect precision -- if your program terminates after 10.2 seconds, that is ok. Anything in the range of 9.5 seconds to 10.5 seconds is fine.

len1860843

2/12/2018 5:31:51 AM

Some points for this assignment are based on algorithm performance. For example, we will give you a test map for urban planning and see how well your program does. The scoring approach is there is a notion of “reasonable” performance, and failure to get a score that high will cost points. For the first question for extra credit, do iterative deepening A* to reduce memory usage. (Bigger deal than the admissibility of the heuristic). For the urban planning problem, you can use either command line arguments or separate programs to select whether to use genetic algorithms or normal hill climbing search. Whichever you choose, you should make it very clear to the TA in a README file how to invoke your program.

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Consult for a business - greedy-balance algorithm

Create an application scenario where the problem can be formulated as Vertex Cover Problem. Use a small problem instance of this application problem as input to illustrate how the approximation algorithm using pricing method Vertex-Cover-Approx

  Design a flowchart that is also a fully functional program

Using Visual Logic, design a flowchart that is also a fully functional program. According to your design, the program must: Continually accept data regarding the purchase of fruit until a sentinel value is entered.

  Write a recursive function member leaf count

Write a recursive function member Leaf Count O for class template BST to count the leaves in a binary tree.

  Explain algorithm analysis summary to upper management

you are requested to create a PowerPoint presentation to explain Algorithm Analysis Summary to upper management.

  Use master theorem to find out its asymptotic bounds

Given T(n) = 16T(n/4) + n2. Use master theorem to find out its asymptotic bounds. Use substitution method to prove its asymptotic bounds

  Write the pseudocode using if-then-else statements

Write the pseudocode using If-Then-Else statements and create a flowchart with a dual alternative decision structure.

  Implement a method to delete every node

Call the structure for the nodes of the tree WordNode, and call the references in this structure left and right. Use Strings to store words in the tree. Call the class implementing the binary search tree WordTree.

  Write algorithm for program to compute the sum of number

Write an algorithm for a program which will satisfy following requirements: - Asks a user how many numbers they want to calculate.

  What do you meant by an rfp

Select a specific category of vertical applications to investigate. Use the Internet and any other sources of information you might have to study some of the different products that are available in that category.

  Find the sum of the degrees of the vertices

Find the sum of the degrees of the vertices

  Identifying the use cases of the system

Identifying the use cases of the system based on the narrative above, and giving a brief description for each of the use cases.

  Design a linear-time algorithm

Design a linear-time algorithm that verifies that the height information in an AVL tree is correctly maintained and that the balance property is in order.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd