AI Algorithms — An Overview

Why We Find AI in Nature

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!

The Ant Colony Optimization Algorithms

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 most straightforward evolutionary algorithm are the ones which have been borrowed from the natural selection mechanisms: the Genetic Algorithms.

The Genetic Algorithms

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

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 higher the score is, the higher the probability is that the individual will be selected for reproduction.

Phase 3: Selection

Phase 4: Crossover

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

For instance instead of getting the following chromosome:

P1’00111101000110001111

They will get this one:

P1’00101101001110001111

Convergence to a Solution

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Acodez IT Solutions

Acodez is one of the leading digital marketing agency in India. We are also a renowned web design and web development company. Visit: https://acodez.in/