FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

2. Non-systematic state space search

DATE OF LAST UPDATE OF THE SITE: 13. 03. 2021, the page is under construction

Introduction

Within this task, the student chooses and implements ONE method of unsystematic search of the state space for solving ONE of the two offered tasks:

  1. Symmetric Traveling Salesman Problem (TSP)
  2. The problem of N queens on the chessboard (N-Queens)

You can apply one of the following non-systematic search methods to the selected task:

  1. genetic algorithm (GA)
  2. hill-climbing algorithm (HC)
  3. simulated annealing (SA)
  4. another method of non-systematic state space searching

In total, there are 8 variants from which students can choose. For variants 1 + A and 1 + B (ie TSP using GA and TSP using HC), templates are prepared that the student can use (details of the template will be discussed at the seminar). The use of a template is optional. The student can choose a programming language of their choice to implement the solution.

Symetric Traveling Salesman Problem (TSP)

A set of cities W and a matrix C of distances between pairs of cities from W are given. The task of a business traveler is to go through these cities and then return to the starting city with minimal travel expenses while visiting each city just once.

Assume that the problem is formulated in Euclidean space, the matrix C of distances between cities is symmetric, ie c (i, j) = c (j, i) (ie passengers can travel between cities in both directions), and the triangular inequality c (i, k) <c (i, j) + c (j, k) for all i, j, kz W.

Using the graph theory apparatus, the problem can be formulated as follows: let G = (V, A) be an undirected graph. In denotes the set of vertices of a graph, these vertices represent cities. A is a set of edges with non-negative evaluations that correspond to the elements of the matrix C of distances between cities. The task is to find the shortest circle in the given graph, which passes through all vertices exactly once (Hamiltonian circles).

Problem of N queens on the board

A chessboard of size NxN and N queens is given. The queen is a very strong piece, she can endanger another piece horizontally, horizontally or diagonally. The task in this task is to place queens on a given chessboard so that they do not endanger each other. The basic assignment is for the chessboard size N = 8 and the wall number of queens. But implement your algorithms for general N and test if you can solve the problem for example for N = 10, N = 20 or N = 100.

Variants 1 + A and 2 + A: TSP or N-queens using a genetic algorithm

Assignment: Design and implement a solution to the traveling salesman problem using a genetic algorithm.

Subtasks:

  1. Design and implement a suitable coding of the TSP problem resp. N-Queens
  2. Design and implement a suitable method for algorithm initialization
  3. Implement the selected selection method
  4. Design and implement an intersection operator
  5. Design and implement a mutation operator
  6. Depending on the selected problem coding, implement a correction operator (that is, implement a correction operator if the problem coding is selected that a correction operator is needed).

A template is ready for the exercise.

Use of template is not required. If you decide to implement an algorithm without a template, ensure visualization of the algorithm in the terminal.

The template includes:

  1. main evolutionary cycle,
  2. population replacement on the basis of selection,
  3. visualization.

Variants 1 + B and 2 + B: TSP or N-queens using the Hill-Climbing algorithm

Assignment: Design and implement a solution to a traveling salesman problem using a hill-climbing algorithm.

Subtasks:

  1. Design and implement a suitable coding of the TSP problem resp. N-queens for solution using the hill-climbing algorithm
  2. Design a purpose function
  3. Define different variants of the environment around a given state
  4. Implement a method for enumerating states in a defined environment
  5. Implement some method to escape from the local extreme, such as restarts

A template is ready for the exercise.

Use of template is not required. If you decide to implement an algorithm without a template, ensure visualization of the algorithm in the terminal.

Variants 1 + C and 2 + C: TSP or N-queens by simulated annealing

Assignment: Design and implement a traveling salesman problem solution using a simulated annealing algorithm.

Subtasks:

  1. Design and implement a suitable coding of the TSP problem resp. N-queens for solution using the simulated annealing method.
  2. Design a purpose function
  3. Implement a probability scheme for accepting a worse state than the current state
  4. Implement a temperature reduction scheme

There is no template ready for this method.

Recommended literature for task 2

[1] Mausam: Slides for a lecture on local search from the University of Washington PDF

[2] Miloš Hauskrecht: Slides for a Lecture on Local Search from the University of Pittsburgh PDF

[3] Lecture slides for BIE-ZUM (pseudo-codes of algorithms)

[4] Norvig, Russel: Artificial Intelligence: A Modern Approach, PDF

[5] Pseudo-codes for algorithms from the AIMA book http://aima.cs.berkeley.edu/algorithms.pdf