AI Algorithms — An Overview

Why We Find AI in Nature

Artificial Intelligence is usually conceived as the manifestation of any non-human intelligence, this later one is described in opposition as “natural” intelligence.

Humans are not the only creatures living on earth which are capable of computing and demonstrating intelligence. Fortunately enough for us, human intelligence is usually regarded as — by far — the highest in their environment.

Nevertheless, other living creatures as insects or animals are known to demonstrate various forms of organizations and “collective” intelligence that fall into the Artificial Intelligence category.

In this article, we will see how powerful can be this Artificial Intelligence which does not involve any machines whatsoever but only biological species.

The idea of “intelligence” is, anyway an anthropomorphic notion, as we do not necessarily wish to conceive — or may not be able to conceive — anything different from our “human” intelligence. Therefore it stays a mysterious domain which is closely bound to the notions of information and organization and especially of “self-organization” which laws and principles are still a complete mystery for us.

The Ants: A Prodigious Source of Algorithms for Humans!

As everyone has probably observed himself or herself at least once in his/her life, ants demonstrate higher levels of an organization. Their perfect and impressive “armies” are able to gather in a very small amount of time any sort of food or material needed by the colony in extremely efficient ways. In fact, there is a very strong AI behind that and it is only relatively recently (1989) that it had been uncovered.

The Ant Colony Optimization Algorithms

In a nutshell, scout ants will randomly walk outside the colony and signal food by leaking pheromones trails. Other ants which will be next to the trails will be attracted by it and will collect food and reinforce the trail by leaking more pheromones.

Since pheromones are volatiles, only the shortest trail will end in becoming selected.

The evaporation of pheromones is the way to constantly remove the bad solutions to the optimization problem ( finding the shortest path between the colony and the food )

Initially, the ant colony algorithm was studied in 1989 by the biologists S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels as a description of a self-organized system.

From the original algorithm, a lot of “man-made” computers algorithms were created, becoming more and more complex with the years. The ants are been modeled as “abstract” agents which are searching for a solution(s) of given optimization problems using individual heuristic processes (so the whole system is called meta-heuristic).

So, starting with the original A.I algorithm observed in nature, several “ant colony” algorithms were created by computer scientists and mathematicians. They belong now to a more general class of algorithms called the Swarm Intelligence algorithms.

Here we represent the basics of the ant colony optimization algorithm as found in nature.

Step 1: A scout ant will initially signal the presence of food (F) to the nest of the colony © by leaking pheromones (red arrows) on the trail that the ant discovered.

Step 2: Following the initial marking, other ants will explore other paths that lead to the food sources and leak pheromones as well on the trail they follow, as a reinforcement. The more pheromone, the more attractive is the trail and the more ants will “travel” through it. In parallel, other scout ants will explore new paths.

Step 3: Because the pheromones will evaporate after a certain amount of time, only the shortest path will remain and this is the path that the ants will take to bring the food to the colony. In other terms, only the most “popular” trail will survive the evaporation of pheromones.

When Darwinism Leads to the Evolutionary Algorithms

The mechanisms of evolution, and in particular the Darwinist theory have been studied for several centuries. The observation of the way some populations evolve to become the fittest category has been the start for a new class of algorithms called the Genetic Algorithms belonging to a more generic category, the Evolutionary Algorithms.

The most straightforward evolutionary algorithm are the ones which have been borrowed from the natural selection mechanisms: the Genetic Algorithms.

The Genetic Algorithms

In nature, a population has offspring which inherits the characteristics of their parents. These characteristics will be added to the next generation. If the parents have better fitness, then the offspring is better than the parents and have a better chance, as well, of surviving.

This is the concept of natural selection as found in nature.

From that, the Genetic Algorithms were created which aim at formalizing- in terms of computer science — that natural concept.

A genetic algorithm will usually consist of 5 phases:

• Initial population phase
• Fitness function selection phase
• Selection phase
• Crossover phase
• Mutation phase

Phase 1: Population

We consider a population P which consists of N individuals P1,…, PN.

Each individual is characterized by their chromosomes C. This is a string from a fixed alphabet named the genes. For example, if we consider the genes to be the alphabet A-Z, a chromosome will consist of a normal word:

C = AWDFRTGHUNJMKLOPSET

In nature, the alphabet consists of all the possible triples among the set of letters {A, G, C, T}. A gene is, therefore, a three-letter word such as AGC or GAT or GGC.

In the Genetic Algorithms, the alphabet is usually binary. So chromosomes will be represented by binary sequences.

Phase 2: Fitness Function

The next phase consists of defining a fitness function. That function will return a score to each individual of the population which will indicate how that individual is able to compete with other individuals regarding a set of constraints.

The higher the score is, the higher the probability is that the individual will be selected for reproduction.

Phase 3: Selection

The selection phase consists in choosing the fittest individuals based on their fitness score. Parents are then selected so they pass their genes to the next generation.

Phase 4: Crossover

During reproduction, a crossover point (in orange) is chosen randomly in the chromosome structure.

P111110110000110001111↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓P200111101000010110110

The two parents, P1 and P2, will have offspring resulting from the exchange between each other of the genes up to the crossover point. This will give a new population of 2 individuals P1’ and P2’.

P1’00111101000110001111P2’11110110000010110110

Phase 5: Mutation

Some offspring may be subject, with low probability, to mutation. This means some of their genes may be flipped.

For instance instead of getting the following chromosome:

P1’00111101000110001111

They will get this one:

P1’00101101001110001111

Convergence to a Solution

The algorithm will converge to a solution when the population has converged, meaning that there are no more significant differences between the offspring and their parents. The population always stays at the fixed size of N, for example, the parents(s) die after the offspring is generated(2) or the least fitted individuals die so to equilibrate the population.

Example

Here we aim at showing a concrete implementation and use of the Genetic Algorithms.

We consider a fitness function f returning the numbers of 1’s in the chromosome. For example, f([11001001])=4 and we consider the chromosome to have fixed length 8.

Our goal is to reach a state where the population will have the maximal possible fittest score, ideally, all individuals in the population have a score of 8.

The following C# code provides an implementation of the basic genetic algorithm and can solve the aforementioned problem.

First, we write a few routines that will generate random data:

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Security.Cryptography;

using System.Text;

using System.Threading.Tasks;

namespace Genetic2 {

class Program {

static int N = 100;

static RNGCryptoServiceProvider rngCsp = new RNGCryptoServiceProvider();

static byte[] buffer = new byte[1];

enum gene {

zero = 0,

one = 1

};

static int generateRandomNumber(int n) {

rngCsp.GetBytes(buffer);

return (Convert.ToInt32(buffer[0]) % n);

}

static gene generateRandomGene() {

rngCsp.GetBytes(buffer);

return (gene)(buffer[0] & amp; 0x01);

}

static gene[] generateRandomChromosome() {

gene[] g = new gene[8];

for (int i = 0; i & lt; 8; i++) {

g[i] = generateRandomGene();

}

return g;

}

static int generateCrossover() {

rngCsp.GetBytes(buffer);

return (Convert.ToInt32(buffer[0]) % 8);

}

We define as well the class individual for the individuals that will be part of the population

They contain several parameters that can tell who are their parents, if they are dead or alive (at a given generation) or if they are currently being selected for reproduction.

The parents are just a structure containing two individuals.

Here there is no notion of sex so the population is hermaphrodite.

class individual

{

public string id;

public gene[] chromosome;

public string parent1_id;

public string parent2_id;

public int n_generation;

public int reproduced;

public bool alive;

public float mutation_rate;

public bool selectedForReproduction;

}

struct parents

{

public individual parent1;

public individual parent2;

};

We maintain the generations inside a global array named hist_populations.

It contains the populations of the N individuals for each generation.

The whole set of generated individuals is maintained in an array named global_population. That array will list any individuals who have been created even if that individual is not alive.

//the population of the n^th generation e.g those who survive

static individual[][] hist_populations= new individual[1000][];

//the entire population included the eliminated individuals

static List<individual> global_population = new List<individual>();

static int curr_generation=0;

static List<parents> list_parents;

This init function initializes the initial population. The initial population has no parents and possess random chromosomes.

public static void init() {

// assign random genes

for (int i = 0; i < N; i++) {

individual ind = new individual();

ind.id = “”+i;

ind.chromosome = generateRandomChromosome();

ind.n_generation = 0;

ind.alive = true;

ind.reproduced = 0;

ind.selectedForReproduction = false;

global_population.Add(ind);

hist_populations[0] = global_population.ToArray();

}

}

The getMaxScoreRate function will compute the amount of the current population that possess maximal fitness. The closer we get to 1, the closer we are to the solution of the problem and the end of the evolution.

static float getMaxScoreRate(int gen) {

int max = hist_populations[gen].Max(ind_ => fitness(ind_));

int S = 0;

for (int i = 0; i < N; i++) {

individual ind = hist_populations[curr_generation][i];

if (fitness(ind) == max) {

S++;

}

}

return (float)(S / N);

}

• The fitness function will return a fitness score, here the number of 1’s in the chromosome of an individual.
• The getWeakest function will return the index of the first element of the weakest individuals of the population, in terms of their fitness function.
• The eliminateWeaks function will mark as non-alive the N/2 individuals which are weaker than the other N/2 individuals of the total population. This is a mechanism of selection. The N/2 individuals eliminated make room for the N/2 new individuals of the new generation. This is obviously a fundamental function otherwise there would be no possible convergence to the fittest population. Such “raw” selection exists in nature, in wildlife for instance, where the weakest animals are not allowed to survive and die from diseases or killed by stronger animals. In our algorithm, there is no notion of “age” but obviously, an individual from a previous generation will see his chance of staying alive diming and diming since his chromosomes are becoming weaker and weaker than the others.

static int fitness(individual ind) {

gene[] chromosome = ind.chromosome;

int score = 0;

for (int i = 0; i < 8; i++) {

score += (int) chromosome[i];

}

return score;

}

static int getWeakest() {

int min = hist_populations[curr_generation].Where(ind_ => ind_.alive == true).Min(ind_ => fitness(ind_));

for (int i = 0; i < N; i++) {

individual ind = hist_populations[curr_generation][i];

if ((fitness(ind) == min) && (ind.alive == true)) {

return i;

}

}

//should never ever happen

return– 1;

}

static individual getIndividualByID(String id_) {

foreach(var ind in global_population) {

if (id_.Equals(ind.id))

return ind;

}

return null;

}

static void eliminateWeaks() {

//we eliminate the least fittest individuals of the population

//so they will not be allowed to reproduce themselves

//half of the population needs to be eliminated

//since parents will duplicate themselves

for (int j = 0; j < N / 2; j++) {

int wi = getWeakest();

hist_populations[curr_generation][wi].alive = false;

getIndividualByID(hist_populations[curr_generation][wi].id).alive = false;

}

}

The reproduce function is the most important of all. It implements the reproduction mechanism.

First, we call eliminateWeaks() so we remove the N/2 weaker individuals.

We generate the parents randomly by calling generateParents() so we create pairs of individuals in the remaining N/2 strongest population.

The pair of parents, individuals selected for reproduction, is contained in the list_parents variable.

The reproduction itself consists of performing the crossover with the two chromosomes of the parents, e.g mixing them using the crossover line.

For each pair of parents, we get two new individuals, namely offspring1 and offspring2.

The population of the new generation consists of the N/2 parents — which are reverted back to a condition of “normal” individuals and unmarked for reproduction — and the N/2 offspring population.

Note that here we did not implement a mutation function for the sake of simplicity.

static void reproduce() {

eliminateWeaks();

This article first appeared on the Acodez