Amazing Algorithms

For Solving Problems in Software


Barry S. Stahl

Solution Architect & Developer

@bsstahl@cognitiveinheritance.com

https://CognitiveInheritance.com

Transparent Half Width Image.png

Favorite Physicists & Mathematicians

Favorite Physicists

  1. Harold "Hal" Stahl
  2. Carl Sagan
  3. Richard Feynman
  4. Marie Curie
  5. Nikola Tesla
  6. Albert Einstein
  7. Neil Degrasse Tyson
  8. Niels Bohr
  9. Galileo Galilei
  10. Michael Faraday

Other notables: Stephen Hawking, Edwin Hubble

Favorite Mathematicians

  1. Ada Lovelace
  2. Alan Turing
  3. Johannes Kepler
  4. Rene Descartes
  5. Isaac Newton
  6. Leonardo Fibonacci
  7. George Boole
  8. Blaise Pascal
  9. Johann Gauss
  10. Grace Hopper

Other notables: Daphne Koller, Grady Booch, Evelyn Berezin

Some OSS Projects I Run

  1. Liquid Victor : Media tracking and aggregation [used to assemble this presentation]
  2. Prehensile Pony-Tail : A static site generator built in c#
  3. TestHelperExtensions : A set of extension methods helpful when building unit tests
  4. Conference Scheduler : A conference schedule optimizer
  5. IntentBot : A microservices framework for creating conversational bots on top of Bot Framework
  6. LiquidNun : Library of abstractions and implementations for loosely-coupled applications
  7. Toastmasters Agenda : A c# library and website for generating agenda's for Toastmasters meetings
  8. ProtoBuf Data Mapper : A c# library for mapping and transforming ProtoBuf messages

http://GiveCamp.org

GiveCamp.png
  bss-100-achievement-unlocked-1024x250.png
  IMG_20190830_222230.jpg

Agenda

  • Best Path Algorithms

    • Ant Colony Optimization
    • Bee Colony Optimization
  • Cost Reduction Algorithms

    • Firefly Optimization
    • Amoeba Optimization
  • AI Models

    • Intro to Optimizing AI Models
    • Training an AI Model Using Amoebas

Best Path Algorithms

Ant Colony Optimization

Ant Colony - Best Path - Animated.gif

Pheromones

  • The Pheromones are the key
    • Greater Usage => More Pheromones
    • Shorter Path Length => More Pheromones Remain
    • More Pheromones => Higher Probability of Usage

Ant Colony Optimization

Ant Colony Optimization Flowchart.png

Ant Colony Optimization

Ant Colony Optimization Psudocode.png
 

Ant Colony Optimization

  • Neighborhood Search
    • Start with random paths
    • Explore neighboring paths based on probability
    • More pheromone = Higher probability of use
    • Can get stuck in a local minima
  • Tweaks
    • Number of ants
    • Pheromones to dispense
    • Pheromone dissipation rate
  • Features
    • Less sensitive to scale
    • Optimality not guaranteed

Bee Colony Optimization

Bee Colony - Best Path - Animated.gif

Types of Bees

Active Workers
Forage on their known path and on a neighboring path

Scouts
Forage on a random path

Inactive Workers
Wait for information from other bees

Bee Colony Optimization

Bee Colony Optimization Flowchart.png

Bee Colony Optimization

Bee Colony Optimization Psudocode.png
 

Bee Colony Optimization

  • Multiple Search types
    • Active Workers perform neighborhood search
    • Scouts perform random search
    • Best known path propogates
  • Tweaks
    • Number of each type of bee
    • Probability of persuasion
    • Visit limit
  • Features
    • Less Sensitive to Scale
    • Optimality not guaranteed

Reducing Costs

Reducing Costs.gif
 
 

Firefly Optimization

Firefly Optimization Flowchart_800x721.png

Firefly Optimization

initialize n fireflies to random positions
loop maxEpochs times
  for each firefly i
    for each firefly j
      if intensity(i) < intensity(j)
        compute attractiveness
        move firefly(i) toward firefly(j)
        update firefly(i) intensity
      end for
    end for
  sort fireflies
end loop
return best position found
 

Firefly Optimization

  • Neighborhood Search
    • Search the area toward best known solution
    • Closer and Brighter: More Attractive
      • Similar to gravity
  • Tweaks
    • Number of fireflies
    • Range of possible values
    • How fast fireflies move
  • Features
    • Works better for linear problems
    • Optimality not guaranteed
    • Can suffer from sparseness problems
MichalewiczFunction.jpg
 
 
 

Amoeba Optimization

Amoeba Optimization - Solutions.png

Amoeba Optimization

Amoeba Optimization Flowchart.png

Amoeba Optimization

initialize the amoeba with n (size) locations
loop maxEpochs times
    calculate new possible solutions
        contracted - midway between centroid and worst
        reflected - contracted point reflected across centroid
        expanded - beyond reflected point by a constant factor
    if any solution is better than the current
        replace worst value with best value from new solution
    else
        shrink (multiple contract) all lesser nodes toward the best
    increment epoch count
end loop
return best position found
 

Amoeba Optimization

  • Neighborhood Search
    • Start with random locations
    • Explore neighbors based on amoeba movement
    • Surround the solution, then contract to it
  • Tweaks
    • Size of the amoeba
      • > # of search dimensions
    • Number of executions
      • Handle local minima
  • Features
    • Optimality no guaranteed
    • Can suffer from sparseness problems
MichalewiczFunction.jpg

What Can We Do With This Stuff?

Linear Data

Positive Only Linear Data.png

Linear Regression Model

Predict the unknown values in a linear equation​

  • Given X (time), predict Y (location)​
    • Y = mX + b​
  • Find the best values for m and b
    • Minimize total error
Regression Model.png

Error Function

Linear Regression - Error Function Plot - Smaller.png

Voter Model

Voter Network Diagram - 673x800.png
  Sigmoid Function.png

ML Demo

Using Amoeba Optimzation to Train an ML Model

 
 
 
 
 
 
 

More Bio-Inspired

  • Roach Infestation Optimization
  • Particle Swarm Optimization
  • Multi-Swarm (Birds) Optimization
  • Bacterial Foraging Optimization
  • Genetic Algorithms

Summary

  • Minimum Cost Optimization
    • Firefly Optimization
    • Amoeba Method Optimization
  • Best Path Optimization
    • Bee Colony Optimization
    • Ant Colony Optimization

Resources