Skip to content

README.en.md

Latest commit

 

History

History
63 lines (33 loc) · 2.63 KB

README.en.md

File metadata and controls

63 lines (33 loc) · 2.63 KB

Artificial Intelligence - Project

Application of Genetic Algorithms in the Knapsack Problem

1. Project Description

The aim of the project is to implement a genetic algorithm (GA) to solve the knapsack problem. The knapsack problem involves selecting specific items in such a way that their total value is maximized while the sum of their weights does not exceed the specified capacity of the knapsack.

2. Project Tasks

(a) Chromosome Structure Implementation

Define the structure of a chromosome representing the solution to the knapsack problem.

(b) Population Creation

Create a random population of chromosomes representing different sets of items in the knapsack.

(c) Fitness Function

Implement a fitness function that evaluates each solution in terms of its value and compliance with the knapsack constraints (total weight).

(d) Selection

Select parents for crossover based on the fitness function. You can use selection methods such as roulette, ranking, or tournament.

(e) Crossover

Perform the crossover operation on pairs of parents to obtain offspring. You can implement various crossover methods.

(f) Mutation

Introduce random changes in the offspring to maintain diversity in the population.

(g) Genetic Algorithm

Implement the main loop of the genetic algorithm, in which you repeat the operations of selection, crossover, and mutation over a certain number of generations.

(h) Result

Record the best solution found by the genetic algorithm.

(i) Tools and Programming Language Selection

Choose the tools and programming language for implementing the genetic algorithm. You can select any programming language, but you cannot use ready-made libraries for solving the knapsack problem.

(j) Report

Prepare a report on the progress of the project. Briefly describe the problems encountered and their solutions at each stage of the GA.

3. Test Data Set

For testing the genetic algorithm in solving the knapsack problem, you can use a sample data set that includes the values and weights of the items and the capacity of the knapsack. Here is a sample data set:

  • Item values: [60, 100, 120, 50, 60, 30, 70, 110, 130, 60, 90, 40, 80, 90, 110, 120, 50, 100, 30, 70]
  • Item weights: [10, 20, 30, 40, 50, 10, 60, 70, 80, 20, 30, 15, 25, 35, 40, 45, 10, 30, 15, 25]
  • Knapsack capacity: 250

4. Submission Format

For evaluation, send the file studentID_firstName_lastName.zip, e.g., 123456_Jan_Kowalski.zip. This file must include the project report in PDF format and the source code file.

(the markdown content was generated and translated by ChatGPT from source PDF file)