Amazing Algorithms

For Solving Problems in Software

Barry S. Stahl

Principal Engineer - AZNerds.net

@bsstahl@cognitiveinheritance.com

https://CognitiveInheritance.com

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, Leonard Susskind, Christiaan Huygens

Favorite Mathematicians

1. Ada Lovelace
2. Alan Turing
3. Tim Berners-Lee
4. Isaac Newton
5. Emmy Noether
6. Johannes Kepler
7. René Descartes
8. George Boole
9. Carl Friedrich Gauss
10. Grace Hopper

Other notables: Blaise Pascal, Daphne Koller, Grady Booch, Evelyn Berezin, Pascal Van Hentenryck

• See my presentation from CodeMash 2025: How the Fediverse Could Save Democracy & Why It Probably Won't

• Hear my thoughts on why a thriving Fediverse is so critical on David Giard's Technology and Friends show.

• Learn more about the Fediverse at fediverse.party.

• Get your own Mastodon account at Join Mastodon.

  • Don't stress on what server to use, just pick one and go. You can always move later.

• Follow me on Mastodon at @bsstahl@CognitiveInheritance.com.

Attempts to make the best possible decision​ based on the model and the data

• Model - Our description of the problem
• Data - Our understanding of the state of the domain

The success of a problem-solving algorithm is often determined before the algorithm even runs -- by how the problem is modeled

• Modeling defines the problem space
  • What’s included & what’s ignored
  • Poor models lead to irrelevant solutions

• Modeling shapes the solution strategy
  • Logical models » OOP or Rules Engines
  • Graph models » traversal algorithms
  • Constraint models » LP or MIP
  • Probabilistic models » Neural/Bayesian Networks

• Modeling can determine tractability
  • Some formulations make problems NP-hard
  • Others reveal polynomial-time solutions
  • Examples
    • Conference Scheduling with LP vs MIP
    • Traveling Salesman with OOP

• Describe these algorithms
  • Show models that work well with each type of problem
  • Describe sample implementations for your use
  • Provide intuition as to why they work as they do

• A family of combinatorial optimization problems
• Goal
  • Select a subset of items from a larger set
  • Without exceeding resource constraints
  • Such that total value is maximized

Store the results of function calls for reuse when the same inputs occur again

• Goal: Compute the nth Fibonacci number
  • F(n) = F(n-1) + F(n-2)
• Naïve Recursion
  • Recomputes each subproblem multiple times
  • O(2ⁿ) Problem - Exponential time
• With Memoization
  • Store results of F(k)
  • Reuse stored values
  • O(n) Problem - Linear Time

• Start at the 1st space on the board​
• While we haven't reached the last space​
  • Add the space to the current path​
  • If the current space has a ladder​
    • Add the end of the ladder to the path​
    • Make that space the current space​
  • Move to the next space on the board​
• Return the completed path through the board

DetermineDistance(s,d)

• Call DetermineDistance(space[0], 0)
• If shorter​ than previously found
  • Set DistanceFromStart property
  • If this space starts a chute or ladder​
    • DetermineDistance(endOfNavigation, distanceFromStart+1​)
  • If not at the end of board​
    • DetermineDistance(nextSpace, distanceFromStart+1)
• Return all spaces with their DistanceFromStart property populated

• Start at the last space on the board​
• While we are still on the board​
  • Add the current space to the path​
  • Set the current space to a space that is a neighbor of the current space and whose DistanceFromStart is space.DistanceFromStart-1​
• Reverse the direction of the path​

Find the best strategy in a multi-player board game​

• Variant of Chutes & Ladders​
  • Player decides whether or not to take a chute or ladder​
• Extremely large Solution Space
  • Impossible to simply try all options

• Shortest Path Algorithm
  • Guarantees shortest path but not necessarily best strategy

• Mixed-Integer Programming Model
  • Requires a mathematical fitness function (can't use a simulation)

• Neural Network
  • Requires a very large training data corpus

Find Solutions by Simulating Darwinian Evolution​

• Each candidate solution is defined by its properties (chromosomes)​
• A fitness function is used to determine which solutions "survive"
  • A simulation may be used as the fitness function
• Surviving solutions may mutate and evolve other solutions​

• Optimal solution may never be found
  • i.e. If a optimality requires a large combination of elements
• Optimum may be found but not recognized
  • If conditions make that solution non-optimal at that moment
    • i.e. If a key feature is not used during the simulation
  • Minimize the liklihood by increasing simulation size

• We need a strategy that will tell us where we

  should move to next, given:

  • Our location on the board
  • The result of our spin
  • The location of our opponents (opt)
  • Our player number (opt)

• Example: If we are on square 45 and spin a:

  • 1 - 46 (no choice)
  • 2 - 47 (no choice)
  • 3 - 48 or 26
  • 4 - 49 or 27
  • 5 - 50, 11 or 28
  • 6 - 51, 12, 29 or 84

• A chromosome represents all of the possible decisions that can be made

• Each gene represents a decision

  • Ideally a gene fully describes a single game state
  • If no decision is possible for a state, there is no gene for that state

• An allele is an option for that decision

  • If there are 3 options for a given state there will be 3 possible alleles for that gene

• Simulations per Generation
  • Controls how often the solutions evolve
  • More simulations make it more likely the best solution will survive

• Generation Count
  • Controls simulation length
  • Optionally look for convergence
    • When does improvement stop?
    • When do significant changes stop during crossover?

• Error (misspelling) rate
  • Controls how frequently genes change allele's during the evolutionary process
  • Higher rates cause greater variations from generation to generation

• Selection strategy
  • Defines which solutions survive and mutate
    • Survive intact - Remain unchanged to next generation
    • Survive mutated - Modified versions survive to next generations
    • Survive recombined - Crossover between two solutions survives

• Implement in your preferred language

  • C# implementation is on GitHub

• Augment to include what place the player is in

  • i.e. Might make different decisions if started 1^st vs 6^th

• Augment to include opponent locations

  • i.e. Might make different decisions if opponents are close to the end

• Define the DNA of another game

  • Recommendation - stick with simpler games to start
  • Avoid games like chess with massive complexity

• A point in multi-dimensional space
• Mathematical representation of a word or phrase
• Encode both semantic and contextual information

• Model: text-embedding-ada-002
• Vectors normalized to unit length
• Use 1536 dimensions

Relate vectors based on the angle between them

• Cosine Similarity ranges from -1 to 1, where:

  • +1 indicates that the vectors represent similar semantics & context
  • 0 indicates that the vectors are orthogonal (no similarity)
  • -1 indicates that the vectors have opposing semantics & context

• Cosine Distance is defined as 1 - cosine similarity where:

  • 0 = Synonymous
  • 1 = Orthogonal
  • 2 = Antonymous

Note: For normalized vectors, cosine similarity is the same as the dot-product

Find distant embeddings

• Assumptions

  • No db of embeddings available to search
  • No understanding of features of the embedding space
    • i.e. changing language changes most dimensions

• What type of models might work?

  • Can we do it logically?
  • Can we brute-force it?
  • Are there hybrid approaches?

• What are the features of each model?

• How do we execute the model(s)?

• Categorical

  • Part of Speech (noun, verb, etc)
  • Register (formal, slang, technical, etc)
  • Morphology (root, compound, phrase)
  • Animacy (inanimate, animate, agentic, collaborative)
  • Scientific Discipline (biology, physical, life/health, etc)

• Continuous

  • Polarity (negative -> positive)
  • Idiomaticity (literal -> idiomatic)
  • Concreteness (abstract -> concrete)

• Other Options

  • Language

What should change to find words distant from the current

• Part of Speech: Noun -> Adverb
• Discipline: Software Engineering -> Philosophy
• Polarity: Neutral -> Highly Positive

You are a simulation of a great linguist.

You classify words/phrases within the following categories:

• Part of Speech (noun, verb, etc)
• Register (formal, slang, technical, etc)
• Scientific Discipline (biology, physical, life/health, etc)
• Morphology (root, compound, phrase)
• Animacy (inanimate, animate, agentic, collaborative)
• Polarity (highly negative, negative, neutral, positive, highly positive)
• Idiomaticity (highly literal, literal, idiomatic, highly idiomatic)
• Concreteness (highly abstract, abstract, concrete, highly concrete)

You identify words/phrases that meet the requested characteristics.

Give me a word or phrase with the following characteristics:

• Primary part of speech is verb
• Register is technical
• Morphology is phrase
• Animacy is collaborative
• Scientific Discipline is biology
• Polarity is highly negative
• Idiomaticity idiomatic
• Concreteness highly concrete

and is not in the following list: "prime genius", "engineer a cooperative symbiosis".

Be sure to only respond with the selected word or phrase, no ceremony.

• We discussed 2 problems:
  • Game strategy - Best move given game state?
  • Semantic Distance - Word to test next?
• What do they have in common?
• What makes them candidates for genetic algorithms?

• Genetic Algorithms "Learn" by simulating Evolution
• The "DNA" represents the decisions that can be made
  • One chromosome per condition (game state)
  • One gene per option (choices from a state)
• Several parameters control how solutions evolve
  • Simulations per Generation - how many changes
    • Fewer simulations increases risk of less-fit surviving
  • Misspelling rate - how often chromosomes change
    • Higher rates cause greater variations
  • Selection strategy - Who survive/mutates
    • Survive intact - Remain unchanged
    • Survive mutated - Modified versions survive
    • Survive recombined - Crossover survives

• 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

• Greater Usage => More Pheromones
• Shorter Path Length => More Pheromones Remain
• More Pheromones => Higher Probability of Usage

• 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

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

• 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

Optimization algorithm used to minimize the cost function of a model

• Shifts the parameters in the opposite direction of the cost gradient

  • The 1st derivative of the cost function

  • Represents the slope of that function

• Hyperparameters include:

  • Number of iterations

  • Learning rate

  • Convergence criteria

• Stochastic Gradient Descent

  • Updates parameters using a subset of data each cycle

Y = mX + B

• Every neuron gets its value from a linear transformation

• Multiple inputs result in a sum of the linear transformations

  • The sum of a linear transformation is linear

• Only linearly-separable functions can be modeled without a non-linear activation

• Parameters: Internal values learned during training

  • Define the relationship between input and output

  • Adjusted to minimize prediction error

• In Linear Regression: Y = mX + b

  • m: Slope (Weight) - The influence of X on Y

  • b: Intercept (Bias) - Shifts the output vertically

• In more complex models:

  • Counts include weights/biases across layers

  • Can capture non-linear relationships

  • Parameter counts are a proxy for complexity

  • GPT-4 uses roughly 1.8 trillion parameters

• X-Axis: The value of the weight (m)
• Y-Axis: The value of the bias (b)
• Z-Axis: The size of the error

The weight (m) often has a greater effect on the error than the bias (b)

• Objective: Minimize the error
  • Error: The difference between the predicted value and the actual value
  • MSE: Mean Squared Error - Avg of the squared differences between predicted and actual
• Means: Gradient Descent Optimization
  • Nearly any Optimization algorithm can be used
  • Gradient Descent is the most common/suited

• Linear Regression - C# Code
• AND Gate Model - Excel
• Maintainability Model - Excel

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

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

• Code Samples

  • Dynamic Programming

  • AI Demos

  • The Algorithms Repo

• My Articles/Presentations

  • Scalable Decision Making

  • AI That Can Explain Why

  • An Example of a Hybrid AI Implementation

  • Building AI Solutions with Google OR-Tools

• Academic Resources

  • Optimization - Coursera Course

  • Clemson University

• Other Articles

  • MSDN Magazine - Firefly Optimization

  • MSDN Magazine - Bee Colony Optimization

  • MSDN Magazine - Amoeba Optimization

  • MSDN Magazine - Ant Colony Optimization

Would you like to try to model a problem from one of your domains?

• Products​
  • Small Vase​
    • 1 oz. clay, 1 oz. glaze​
    • Sells for $3.00 each​
  • Large Vase​
    • 4 oz. clay, 2 oz. glaze​
    • Sells for $9.00 each​

• Inventory​
  • Clay - 24 oz.​
  • Glaze - 16 oz.​

• Goal
  • Maximize Revenue

• Define Constraints that the Solution Must Satisfy​
  • Use these constraints to limit the search space​
    • More constraints = smaller search space
      • Solutions that exist are found faster
      • May not find a feasible solution

• Add an Objective Function to Improve Solutions​
  • All constraints must be satisfied first​
  • Objectives are a goal relative to an equation​
    • i.e. Maximize revenue where r = 3X + 9Y