top of page

### Artificial Intelligence

Artificial Intelligence was an introductory survey of the field of artificial intelligence. Select course topics can be found below:

• Rational Agents

• Behavior Trees

• Uninformed Search (e.g. UCS)

• Informed Search (e.g. A*)

• Constraint Satisfaction Problems

• Local Search

• Zeroth & First-Order Logic

• Bayesian Networks

• Markov Models

• Learning by Example

• Artificial Neural Networks

• Cognitive Architectures

• Ethics in AI

Genetic Algorithm

### Genetic Algorithm

In addition to exams, problem sets were used to test knowledge and give hands-on experience working with techniques covered in class. An example problem from one problem set is laid out here:

â€‹

Description:

You are going on a hiking trip, and there is a limit to the things you can bring. You have two things: a backpack with a size (the weight it can hold, that is) and a set of boxes with different weights and different importance values.

Weight list:              [20, 30, 60, 90, 50, 70, 30, 30, 70, 20, 20, 60]     (12 items)

Importance list:       [6, 5, 8, 7, 6, 9, 4, 5, 4, 9, 2, 1]

Goal:

The goal is to fill the backpack to make it as valuable as possible without exceeding the maximum weight (250).

1) Define the problem in the context of genetic algorithms

2)  Provide the genome for the problem

3) Define fringe operations

4) Cull your population by 50% at every generation

â€‹

Solution:

My approach is laid out here:

â€‹

The problem can be formalized as a genetic search process as follows: Let X be the set of possible items and let A = {x_1,...,x_n} be the power set of X. Then n = 2^{12}.

Define a genome/chromosome to be an element x_i of A, represented by binary sequence of 12 inclusion/exclusion variables.

Define the fitness function f to be:

- f(x_i) = {sum of importance values ("precedence") of items in i} for sum <= limit. 0 for sum > limit.                 - Alternatively, the sum over precedences times kronecker delta which is equal to 1 if the element is in x_i         and zero otherwise

Initialize the population of size N < n

Cull the bottom 50% with the lowest fitness functions

Of the remaining population, take each chromosome and randomly permute whether or not it has an item in it

Uniform distribution can be used, but also can randomly permute giving higher weights to common                items. I.e. if 9 of 10 of the strongest 50% all have item 4 in common, make this less likely to permute

Repeat for desired number of iterations or until a given efficiency is reached by at least 1 chromosome

â€‹

Implementation:

I implemented the above solution in Python utilizing NumPy and PyPlot. Below, a chart of the fitness of each chromosome in each iteration can be seen, along with progress charts of the most/least fit chromosomes.

bottom of page