also reachable via 2 other paths through the graph
cast off

IOPS

17.10.2023 · AE531017
Initiation into Optimization & Problem-Solving
scan to join on your phone
> click / swipe / arrow keys to begin_

Constraints

17.10.2023 · AE531017
Parameters & Constraints

Heuristics

27.11.2023 · AE531127
The term "heuristics" comes from the Greek word "heuriskein," which means "to find" or "to discover." This term reflects the idea of finding or discovering solutions through intuitive or trial-and-error methods. 

Problem & Solution

17.10.2023 · AE531017
In engineering, a problem P is defined by an objective function that needs to be optimized, a vector of parameters that can be adjusted, and constraints that must be satisfied.

The solution S is the optimal set of parameter values that achieve the desired optimization while staying within the bounds of the constraints.

Etymology

29.10.2023 · AE531029
Middle English: from Old French constraindre, from Latin constringere ‘bind tightly together’.
dall-e 3:
dall-e 3: "illustration on black background of archimedes discovering the physical law and crying with face full of enthusiasm the word EUREKA (word should be depicted in the comics-like bubble"

Etymology

28.11.2023 · AE531128
The term "heuristics" comes from the Greek word "heuriskein," which means "to find" or "to discover." This term reflects the idea of finding or discovering solutions through intuitive or trial-and-error methods.

Meta-Problem

17.10.2023 · AE531017
What problem is worth time of Your life ?

Mathematico-logical heuristics

17.10.2023 · AE531017
Mathematico-logical heuristics involve using structured mathematical or logical methods to solve problems. They include techniques like calculus for optimizing functions, linear programming for maximizing or minimizing linear objectives under constraints, and 3-SAT for solving complex logical puzzles. These heuristics apply rigorous mathematical rules and logic to break down and solve problems step-by-step. They are especially useful for structured problems where precise, logical solutions are needed, like in operations research, computer science, and engineering.
picture of
picture of "problem", black background

problem(s)

17.10.2023 · AE531017
A problem P can be defined as a situation or scenario where a particular system, device, or process is not performing as desired, leading to suboptimal or undesired outcomes. In a design & engineering context, P is typically framed in terms of:

Vector of Parameters: This is a set of variables or conditions that characterize the system or scenario. They can be input conditions, system states, or any other relevant metrics that describe the system. 

Objective Function: This is a mathematical function that quantifies how far the current system's performance is from the desired performance. The goal is usually to minimize or maximize this function. 

Constraints: These are the bounds or limitations within which the system operates. In engineering problems, constraints can arise from physical limitations, safety requirements, budgetary restrictions, etc. The solution must satisfy these constraints.

Reflectio: Constraint types

29.10.2023 · AE531029
What types of constraints do You take into account when You:

make a decision D

when You solve a problem P 

???

dalle-e 3: essence of hilbert problem
dalle-e 3: essence of hilbert problem "topology of algebraic curves and surfaces", black background

Hilbert problem(s)

17.10.2023 · AE531017
The Hilbert Problems are a set of 23 mathematical challenges presented by the German mathematician David Hilbert in 1900. Aimed at defining future research directions, these problems span various areas of mathematics. While some were clearly stated, others were more open-ended. Over the decades, a majority of these problems have been resolved, significantly advancing mathematical knowledge. Some led to the establishment of entire new fields of study. Unresolved - as of AE53 - Hilbert problems:

Mathematical Treatment of the Axioms of Physics

Rigorous Foundation of Schubert's Enumerative Calculus

Topology of Algebraic Curves and Surfaces

Analysis of Solutions of Variational Problems

Calculus

27.11.2023 · AE531127
Calculus-based heuristics, like Newton's method or gradient descent, use principles of calculus to find solutions to complex problems. They involve calculating slopes or gradients to understand how a function changes. For instance, gradient descent moves towards the lowest point of a function, similar to finding the bottom of a valley - this point is often the best solution. These methods are powerful for optimizing problems, like in machine learning or economics, where finding the most efficient point is crucial.

Constraint types

29.10.2023 · AE531029

logic / contingency

space

time

energy

computational complexity

human resources

material resources

eco(log|nom)ical constraints

socio-political

psycho-cognitive

legal

moral

etymology of the term 'problem'

17.10.2023 · AE531017
From Middle English probleme, from Middle French probleme, from Latin problema, from Ancient Greek πρόβλημα (próblēma, “anything thrown forward, hindrance, obstacle, anything projecting, a headland, promontory”), from προβάλλω (probállō, “to throw or lay something in front of someone, to put forward”), from προ- (pro-, “in front of”) + βάλλω (bállō, “to throw, to cast, to hurl”).

[note the etymologic similarity to word "project":  from Latin projectum ‘something prominent’, neuter past participle of proicere ‘throw forth’, from pro- ‘forth’ + jacere ‘to throw’)]

Alltag problem(s)

17.10.2023 · AE531017
Divide in couples and discuss with Your colleagues cases when You use the word problem in daily life. Pose Yourself questions like "What was the last problem I solved ?", "What was the last problem I didn't manage to solve "? etc.

Newton's method

27.11.2023 · AE531127
Newton's Method is a calculus-based technique to find the roots of a function, where the function equals zero. It starts with a guess and repeatedly applies a formula to get closer to the root. It uses the function's slope (derivative) to improve each guess. It's effective for smooth, continuous functions but can fail for functions with no derivative, flat slopes, or multiple roots near each other. It's great for precise, math-heavy problems but not for erratic or non-differentiable functions.

Gradient descent

27.11.2023 · AE531127
Gradient Descent is a method used to find the minimum of a function. Imagine walking downhill towards the lowest point in a valley—that's what this method does mathematically. It calculates the gradient (the slope) of the function and takes steps in the direction that decreases the function's value. It's powerful for optimizing in machine learning and economics. However, it struggles with functions having many valleys (local minima) or plateaus, and might not find the absolute lowest point (global minimum).
dall-e 3: 'generate picture which illustrates the best the essence of
dall-e 3: 'generate picture which illustrates the best the essence of "riemann hypothesis"'

Millenium Problems

26.10.2023 · AE531026
The Millennium Problems are seven mathematical challenges established by the Clay Mathematics Institute in 2000, each with a prize of one million dollars for a correct solution. These problems represent some of the most persistent and critical unsolved issues in mathematics, spanning areas such as number theory, geometry, analysis, and fluid dynamics. Only one of the problems, the Poincaré Conjecture, has been solved so far. Unresolved - as of AE53 - ones are:

Birch and Swinnerton-Dyer Conjecture

Hodge Conjecture

Navier–Stokes Existence and Smoothness

P vs NP Problem

Riemann Hypothesis

Yang–Mills Existence and Mass Gap

3-SAT Problem

17.10.2023 · AE531017
The 3-SAT (3-Satisfiability) problem is a classic question in computer science and mathematical logic. It's a specific type of Boolean satisfiability problem. In 3-SAT, you're given a formula composed of several clauses, where each clause is a disjunction (an "OR" operation) of exactly three literals (variables or their negations). The challenge is to determine if there exists an assignment of truth values (true or false) to the variables that makes the entire formula true. This problem is known for being NP-complete, meaning it's easy to check a solution but potentially very hard to find one, especially as the number of variables increases. This characteristic makes 3-SAT important in theoretical computer science, particularly in studies related to computational complexity.
dall-e 3:
dall-e 3: "essence of wicked problem, black background"

wicked problems

26.10.2023 · AE531026

No Definitive Formulation

No Stopping Rule

Solutions Are Not True-or-False

No Immediate and No Ultimate Test

Every Solution is a 'One-Shot Operation'

No Enumerable (or Exhaustively Describable) Set of Potential Solutions

Every Wicked Problem is Essentially Unique

Every Wicked Problem Can Be Considered to Be a Symptom of Another Problem

The Existence of a Discrepancy Representing a Wicked Problem Can Be Explained in Numerous Ways

The Planner Has No Right to Be Wrong

13 teacher-proposed D&C problems

26.10.2023 · AE531026
This is the set of problem(s) to which I expose all my D&C students since AE50.

Hopefully, at least 1 will be "solved" during my lifetime, 2 during Your lifetime and 3 during lifetime of my children.

Closing the Door to Hell

26.10.2023 · AE531026
The "Door to Hell" or the Darvaza Gas Crater is a natural gas field located in the Karakum Desert in Turkmenistan. It has been burning continuously since 1971 when it was set on fire by Soviet geologists to prevent the spread of methane gas after a drilling rig collapsed into it.

Status: solvable
Approach: CAD, scientific modeling, few telephone calls, trip to Turkmenistan

Fremen Stilsuit

26.10.2023 · AE531026
The Fremen stilsuit, native to the desert planet Arrakis *, is a marvel of engineering. Designed to conserve moisture, this full-body attire reclaims sweat, breath, and waste, converting them into drinkable water. Its black, skin-tight material is layered to reduce heat exposure and prevent water loss. Tubing systems distribute reclaimed water to catchpockets, from which the wearer can drink. Breath filters purify and reclaim moisture, while a nose plug ensures no moisture escapes. Built for desert survival, the stilsuit ensures the Fremen can thrive in Arrakis' harsh environment, making the most of every precious drop of water.

* also known as Terra, Gaia or Zem etc. during AD and AE epochs

Inspiration: Frank Herbert, Dune

Central Problem of Roboethics

26.10.2023 · AE531026
The central problem of roboethics is defined as follows: AI & robot engineers aim to construct beings which will transcend the faculties of human  beings, on the other hand, some unethical acts should be made impossible to  execute for such artificial beings (Hromada, 2011)

Note: the central problem is equivalent, mutatis mutandi, to much more famous "AI Alignment" problem

Young Lady's Illustrated Primer

26.10.2023 · AE531026
The Primer is an almost magical, book-like solarpunk artefact with embedded personalized adaptive generative teacher avatar so advanced that it is able to catalyse, by means of education, a transformation of a traumatized orphan into a Queen.

Status: solvable (provided that there is at least one vacant 👑 around)
Approach: fine-tuning of Large Language Models, speech technologies, Raspberry Pi
Inspiration: Neal Stephenson (Diamond Age: or Young Lady's Illustrated Primer)

Cracking the Voynich Manuscript

26.10.2023 · AE531026
Voynich Manuscript is a corpus of unknown origin written down in unique graphemic system and potentially representing phonic values of unknown or potentially even extinct language.

Status: solvable
Approach: Multi-modal artificial intelligence, trans-disciplinary research, classic cryptographic methods

Tempelhof Biosphere

26.10.2023 · AE531026
Geodetic dome providing a protective membrane around highly diversified biosphere above, around and  below Berlin's Tempelhofer Field. 

Status: solvable
Approach: material research, architecture, corruption

Self-optimization of communities and societies

26.10.2023 · AE531026
Interconnect processes of opinion aggregation, expertise integration and decision-making so that at least some future social and political systems are more equitable, adaptable and less prone to "extinction through stupidity".

Status: wicked
Approach: try in smaller community, then expand

Common Eco(log|nom)ical Protocol

26.10.2023 · AE531026
Common Ecological Protocol is a SDG *-inspired set of positives ("DOs") and negative ("DON'Ts") principles establishing a planetary-wide Nash equilibrium between all human, institutional, corporate, artificial and organic agents.

* SDG = United Nation's Sustainable Development Goals

Approach: Game-Theoretical and Agent-based simulations
Status: wicked but solvable through (enforced) consensus
dalle-3:
dalle-3: "picture of space elevator platform attached to artificial island in equator region with strongly intertwined carbon nanotube fiber, black background"

Space Elevator

26.10.2023 · AE531026
A space elevator is a proposed transport system connecting Earth's surface directly to space using a tethered cable. Primarily envisioned to reduce exorbitant rocket launch costs, it aims to provide sustainable and energy-efficient space access. The concept requires a geostationary anchor in space and a base on Earth, connected by a carbon nanotube or similar high-strength cable. Centrifugal forces from Earth's rotation keep the cable taut. Elevator cars, powered by solar energy or lasers, would climb this cable. 

Status: uncertain but decidable
Approach: material research, modeling, fractal architecture

The Tangle

26.10.2023 · AE531026
The tangle is circle with 1m radius containing different vertically stacked herbs, veggies, fruits  and mushrooms which maximize nutritive yield beneficial for human all year long and minimizes the amount of external intervention.

Inspiration: Neal Stephenson (Anathem)
Aquatic Alternative: The Aquarium
dall-e 3: 'picture of bilbo passing to frodo the scroll with a PSI symbol on it, saying
dall-e 3: 'picture of bilbo passing to frodo the scroll with a PSI symbol on it, saying "the ring is yours"'

Elliptic Curve Discrete Logarithm Problem

26.10.2023 · AE531026
Unsolvability of ECDLP is the pillar on which modern asymmetric cryptography (e.g. cryptocurrencies, communication with products of military-industrial complex etc.) stands.

Status: uncertain and potentially meta-unsolvable *
Approach: apt install sagemath, pen & paper, hope

* proof of ECDLP unsolvability is equivalent to solving the P = NP Millenium Problem
picture of
picture of "the seed", the universal nano-assembler in process of creating its own copy. has tree-like, fractal form of a dandelion seed with the MEMS nanocomputer at its base, spherical buckyball energy source in the middle and many robotic arms on the top

The Seed

26.10.2023 · AE531026
The Seed, or Universal Nano-Assembler, is a programmable, portable, self-sustainable matter compiler of non-organic origin able to reorganize molecules of its envelopping substrate in such a manner that it is able to create its own copy in less than one hour.

Status: nature can do it
Approach: MEMS, DNA-computing, nanotech, protein design, AGI
Inspiration: Eric Drexler (Engines of Creation)
The core of the microfusor is a solid carbon-based magnetic confinement lattice similar to hobberman's sphere  filled with  hydrogen isotope fuel.
The core of the microfusor is a solid carbon-based magnetic confinement lattice similar to hobberman's sphere filled with hydrogen isotope fuel.

H-microfusor

26.10.2023 · AE531026
H-microfusor is a reactor for deuterium/tritium nuclear fusion whose size does not exceed 1 cubic meter and which is able to persist in the breakeven state (Q>=1) for at least 1 second.

Approach: scientific modeling, CAD, nanotechnology
Status: solvable 
picture showing depictions of these problems
picture showing depictions of these problems "Radioactive waste disposal", "Liberation from fossil fuel dependency", "Language extinction", "Weltverständlichmachung","unf*cking the wohnnungsmarkt", "the clock reform" in different segments of the picture, black background

10 student-proposed D&C problems

26.10.2023 · AE531026

Radioactive waste disposal

Liberation from fossil fuel dependency

Language extinction

Weltverständlichmachung

Unf*cking the Wohnungsmarkt

...

...

...

...

The Clock Reform

Taxonomy of Problems

26.10.2023 · AE531026
 
"Illustration on a black background depicting the concept of 'constraint programming'. A set of interconnected nodes, each labeled as a variable, with chains or links representing constraints. Some nodes glow to indicate they are satisfying their constraints, while others are dim to show they aren't."

Constraint programming

29.10.2023 · AE531029
Constraint programming is a programming paradigm where relationships between variables are expressed as constraints. The objective is to find values for these variables that satisfy all given constraints. It is particularly useful for solving combinatorial problems, such as scheduling, planning, and resource allocation, where traditional algorithms might be inefficient. Instead of specifying steps to achieve a solution, one defines the desired properties of a solution, and the system determines a valid assignment, if one exists.

Nature-inspired heuristics

17.10.2023 · AE531017
Nature-inspired heuristics are problem-solving methods modeled after natural processes. Like how birds flock or bees forage, these algorithms mimic nature to tackle complex problems. They use strategies like evolution, ant colony behavior, or bird flocking to find good solutions, blending randomness with specific rules from nature. These methods are useful for tough problems where traditional approaches might fail, creatively applying nature's wisdom to areas like computer science, engineering, and logistics to find efficient, often surprising, solutions.
pyschedule example
pyschedule example

Python libraries

29.10.2023 · AE531029

https://github.com/python-constraint/python-constraint

https://github.com/timnon/pyschedule

Note: install the most recent fork, (e.g. pip3.10 install "pyschedule"@git+"https://github.com/ppoile/pyschedule/#subdirectory=src")

Constraint Satisfaction Problem

29.10.2023 · AE531029
A Constraint Satisfaction Problem (CSP) is a mathematical problem defined by a set of variables, a domain of possible values for each variable, and a collection of constraints specifying permissible combinations of values. The goal is to assign values to the variables such that all constraints are satisfied. Common examples include the Sudoku puzzle, where each cell is a variable, digits 1-9 are the domain, and the rules of Sudoku are the constraints. Other examples:

eight queen problems

map coloring problem

Exercise: Adam and Eve scheduling

29.10.2023 · AE531029
Adam and Eve are happily married and have two cute sons, Cain and Abel. In general they love each other, but sometimes divirgent opinions relating to house management lead to unnecessary conflicts. To reduce such conflicts, Adam proposes to optimize, starting with following facts:  there are four rooms (kitchen, bath, living room, sleeping room) in their house and they want to have each room in an absolutely clean state at least once in a week. Cleaning of sleeping room and bathroom necessitate investment of 2 hours each, cleaning of living room and kitchen  costs 3 hours each. In order to keep family healthy & restauration costs low, a hot meal is cooked at least 4 times in a week and children also demand one cake a week. Cooking takes 1 hour, baking 2 hours. After cooking or baking, kitchen becomes dirty and Eve demands that kitchen is clean on Sunday evening.  Adam has one hour time on Monday and Wednesday, three hours time on Thursday and fours hours time on each weekend day, Eve has two hours on Tuesday, three hours on Friday and four hours on each weekend day. Ideally, they would like to maximize the amount of time they invest into cleaning & cooking.

Optional: Act of bringing little Cain & Abel to a playground for two hours results in less entropy at home and thus reduces living room cleaning cost to two.

Simulated annealing

17.10.2023 · AE531017
Simulated Annealing is a technique for finding good solutions to tough problems. It's like trying different temperatures to shape a metal perfectly. At first, it allows big changes (high temperature), even if they seem wrong, to explore different options. Gradually, it cools down (lowers the temperature), making smaller, more careful adjustments. This process helps avoid getting stuck with a not-so-great solution (local optimum) and aims for a better one, although it might not always be the best possible (global optimum).

Assignment

29.10.2023 · AE531029
Everyone: define tasks (and their lengths), resources (and their availability), precedence relations (if any), capacity constraints (if any) and costs of optional tasks (if any)

IOPS group: find the optimal solution using some constraint programming library (GPT4 can show You how to use it)

Solution

14.11.2023 · AE531114
#Adam has one hour time on Monday and Wednesday, three hours time on Thursday and fours hours time on each weekend day, Eve has two hours on Tuesday, three hours on Friday and four hours on each weekend day.  Define pyschedule resources with correctly defined periods and horizons.

#Monday: Adam x 1
#Tuesday:  Eva x 2
#Wednesday: Adam x 1
#Thursday: Adam x 4
#Friday: Eva x 3
#Saturday: Both x 4
#Sunday : Both x 4

from pyschedule import Scenario, solvers, plotters, alt

# Define the scenario
S = Scenario('household_chores', horizon=15)  # Two weeks

# Define the resources, resource costs are not obligatory but it's more fun with them
adam = S.Resource('Adam',periods=[0,3,4,5,6,7,11,12,13,14])
eve = S.Resource('Eve',periods=[1,2,8,9,10,11,12,13,14])

kitchen=S.Resource('kitchen')

# Define the tasks and their durations
task_costs = {
    "meal1": {"length":1,"delay_cost":1},                # 1 hour, schedule towards beginning of the week
    "meal2": {"length":1,"delay_cost":1},             
    "meal3": {"length":1,"delay_cost":-1},               
    "meal4": {"length":1,"delay_cost":-1},               # 1 hour, schedule towards end of the week
    "bake": {"length":2,"delay_cost":0},                  # 2 hours (1 cake)
    "sleeping_room": {"length":2,"delay_cost":0},  # it seems there is a bug for tasks longer >1 
    #"CSR1": {"length":1,"delay_cost":0},          # one way how to address the bug is to split long tasks into sub-tasks coupled by tight preference constraints
    #"CSR2": {"length":1,"delay_cost":0},          # 
    "bathroom": {"length":2,"delay_cost":0},       # 2 hours
    "living_room": {"length":3,"delay_cost":0},    # 3 hours
    "clean_kitchen": {"length":3,"delay_cost":0}   # 3 hours
}

tasks={}
# Define alternative resources for each task
for task,costs in task_costs.items():
    print(task,costs)
    tasks[task] = S.Task(task,length=costs['length'],delay_cost=costs["delay_cost"])      #create new task
    tasks[task] += adam | eve               #assign resources to newly created task

#additional task-resource attributions
tasks["clean_kitchen"]+=kitchen
tasks["meal1"]+=kitchen
tasks["meal2"]+=kitchen
tasks["meal3"]+=kitchen
tasks["meal4"]+=kitchen
tasks["bake"]+=kitchen

#tight precedence constraints
#S += tasks['CSR1'] <= tasks['CSR2']

#optional tasks
#tasks['playground'] = S.Task('playground',length=2,schedule_cost=-1)
#tasks['playground'] += alt(adam,eve)

#additional constraints
S += tasks['meal1'] < tasks['clean_kitchen'] 
S += tasks['meal2'] < tasks['clean_kitchen'] 
S += tasks['meal3'] < tasks['clean_kitchen'] 
S += tasks['meal4'] < tasks['clean_kitchen'] 
S += tasks['bake'] < tasks['clean_kitchen'] 

# Solve the scenario
solvers.mip.solve(S,msg=1,kind='GUROBI')

print(S)
print(S.solution())
print(adam.periods)
# Plot the schedule
plotters.matplotlib.plot(S)

Ant colony optimization

17.10.2023 · AE531017
Ant Colony Optimization is inspired by how real ants find the shortest paths to food. In this method, virtual ants roam through possible solutions, leaving pheromone trails. Stronger trails attract more ants, suggesting better solutions. Over time, the best paths have more pheromones, guiding ants towards them. It's great for complex problems like routing or scheduling, where finding the best route matters. It's like following a trail to the best answer based on the collective wisdom of many trials.
picture of
picture of "problem about which it is impossible to find out if it can be solved or not", black background

unsolved

26.10.2023 · AE531026
Unsolved problems are problems for which we neither have a solution, nor know whether such solution can be found.

solvable

26.10.2023 · AE531026
P is solvable if, at some point in time, a proof will be provided that solution to P can be found.

unsolvable

26.10.2023 · AE531026
P is unsolvable if, at some point in time, a proof will be provided that P does not have solution.
illustration of
illustration of "unsolvable and undecidable problem which leads to madness", black background

fatal

26.10.2023 · AE531026
Problem P is "fatal" if no proof could ever be provided whether P is solvable or unsolvable. 

It is impossible to tell about problem if it is "fatal". That's why it is fatal ;)

Evolutionary optimization

17.10.2023 · AE531017
Evolutionary Optimization mimics natural selection, like how animals evolve. Imagine a population of potential solutions. Those fitting the problem best (like the fittest animals) are chosen to 'reproduce.' They mix and mutate to create new solutions or 'offspring.' Over generations, this process 'evolves' better solutions, as unfit ones are discarded. It's a trial-and-error method using principles of evolution, effectively finding good solutions for complex problems by simulating survival of the fittest in a virtual environment.

Genetic Algorithm

28.11.2023 · AE531128
A Genetic Algorithm is a method in evolutionary optimization that solves problems by mimicking natural evolution. Imagine a survival contest where each participant (solution) has traits (parameters). These solutions breed and mutate, creating new generations. The fittest solutions, judged by a fitness function, survive to breed again. Over time, this process 'evolves' increasingly effective solutions. It's like nature's trial-and-error but used for complex problems like route planning, where finding the best or a good-enough solution is essential.

Selection

28.11.2023 · AE531128
In evolutionary optimization, selection is like a survival test for candidate solutions, deciding which ones get to 'reproduce.' Selection operators are the rules determining who passes this test. They might choose the fittest solutions (those solving the problem best) or sometimes include random or less fit ones for diversity. 

Variation

28.11.2023 · AE531128
In evolutionary optimization, variation is the process of introducing diversity into the population of solutions. Like genetic mutations and breeding in nature, it involves altering the 'genes' (parameters) of candidate solutions to create new, different ones. This can be done through mutation (changing some parameters) or crossover (mixing parameters from two solutions). Variation is crucial for exploring new solutions and avoiding getting stuck with suboptimal ones, much like how biological diversity is key to the survival and evolution of species.

Replication

28.11.2023 · AE531128
In evolutionary optimization, replication is like making copies of the best solutions. Imagine a survival contest where top performers are cloned. These copies then undergo changes (mutations) or combine features (crossover) to create new solutions. Replication ensures good traits are passed on, increasing chances that future generations will perform even better. It's used in algorithms to solve complex problems, where keeping and tweaking successful solutions gradually leads to finding the best or a very good answer.

Selection operators

28.11.2023 · AE531128

elitism: select N most fit individuals and copy them to next generation

roulette-wheel: probability of survival into next generation is proportional to indvididual's fitness

tournament...

Individual|Genotype|Chromosome

28.11.2023 · AE531128
In evolutionary optimization, an "individual," also termed a "genotype" or "chromosome," is a candidate solution to a problem. Think of it like a recipe where each ingredient is a parameter of the solution. These parameters are the "genes" of the individual. Together, they define how the solution behaves or performs. Like in natural evolution, these individuals can be altered (mutated) or combined (through crossover) to create new solutions, in the quest to find the best or most effective answer.

Population

28.11.2023 · AE531128
Population is a set of individuals.

Mutation

28.11.2023 · AE531128

for numeric genes: additive mutation, multiplicative mutation, complex (imaginary) mutation

for symbolic ones: removal, addition or replacement of a symbol; metathesis (e.g. MORF -> FORM)

NOTE: Mutation rates often fall in the range of 0.5% to 1% per gene. This rate is low enough to prevent excessive random search (which can disrupt good solutions) and high enough to introduce diversity and enable the algorithm to explore new areas of the solution space.

Crossover

28.11.2023 · AE531128
Crossover

Fitness function

28.11.2023 · AE531128
In evolutionary optimization, a "fitness function" is like a scoring system that rates how good each candidate solution (or 'individual') is at solving the problem. Think of it as a judge in a competition, evaluating participants based on how well they meet certain criteria. The higher the score, the better the solution. This function is crucial because it guides the selection process, helping to decide which solutions should be kept, discarded, or combined to create the next generation of solutions.

Genetic programming

28.11.2023 · AE531128
Genetic Programming (GP) is a type of evolutionary optimization where programs themselves evolve to solve problems. Imagine a computer automatically writing and modifying its own code to get better at a task. In GP, each 'individual' is a computer program. These programs are tested for their ability to solve a problem, and the best ones are modified (mutated) or combined (crossed over) to create new programs. Over generations, this process evolves programs that become increasingly effective at the task.

Grammatical evolution

28.11.2023 · AE531128
Grammar Evolution is a type of evolutionary optimization where solutions are generated using a predefined set of rules, like a grammar in language. Imagine creating sentences using grammar rules, but here, the 'sentences' are computer programs or formulas. Each solution must follow these rules, ensuring they make sense. Like in genetic programming, these solutions evolve over generations, becoming better at solving a problem. It's particularly useful when solutions need a specific structure or format, allowing for complex, yet orderly, evolution.

Caching

28.11.2023 · AE531128
Caching is a technique used in computing to store frequently accessed data in a readily available location for quick retrieval. It's like having a small, fast memory space for storing the most commonly used information, reducing the need to repeatedly access slower storage areas. In problem-solving, caching is crucial for enhancing performance and efficiency. By remembering previously computed results, systems can avoid redoing complex calculations, significantly speeding up the process of solving repetitive or similar problems. This approach is widely used in software development, web browsing, and data processing.

Linear Programming

14.11.2023 · AE531114
Linear Programming (LP) is a mathematical method used to find the best outcome in a model whose requirements are represented by linear relationships. It's like playing a game where you need to achieve the highest score (maximize) or the lowest score (minimize) under certain rules. These rules are your constraints, like how much money you can spend or how many hours you have. The score you're trying to optimize is called the objective function, and it's also a linear equation. LP helps you figure out the best way to play this game, balancing all the rules, to achieve your goal, whether it's making the most profit, using the least resources, or something similar. It's a powerful tool for decision-making in business, engineering, economics, and more.

solution(s)

17.10.2023 · AE531017

Human heuristics

17.10.2023 · AE531017
Human heuristics are simple, intuitive rules we use to make quick decisions, like "avoid dark alleys at night." They are based on our experiences and common sense, helping us navigate everyday choices efficiently without much thought. Useful in fast-paced or uncertain situations, these shortcuts can lead to good enough decisions. However, they're not always reliable for complex, critical decisions or in unfamiliar contexts, as they can oversimplify situations and be influenced by biases, potentially leading to poor choices.

etymology of the term 'solution'

17.10.2023 · AE531017
The word "solution" has its roots in Latin, deriving from the word “solutio.” The etymology can be broken down as follows:
  • Latin "solutio": Meaning a loosening or unbinding. This comes from the verb “solvere,” which means to loosen, untie, or dissolve.
  • Latin "solvēre": This is a compound of “sol-,” a variant of “se-” (apart), and “luere” (to wash or to loosen).
Over time, the meaning of "solution" has evolved and broadened. In English, it has been used since the 14th century to refer not just to the act of dissolving a substance in a liquid, but also to the means of solving a problem or answering a question. The sense of finding an answer or explanation encapsulates the idea of resolving a complex situation, untangling its components to reach a clear understanding or resolutionIn summary, the etymology of "solution" reflects a journey from the physical act of loosening or dissolving, through to the more abstract notion of resolving problems and finding answers.

Advice 0

17.10.2023 · AE531017
Used as a general rule in chemistry; the old alchemical principle "similia similibus dissolvuntur" meaning "like dissolves like" refers to the ability of polar or non polar solvents to dissolve polar or non polar solutes respectively.

Engineer's solution

26.10.2023 · AE531026
In engineering, the solution S is that vector of P which minimizes (resp. maximizes) the value of objective function F.

Simplex Algorithm

14.11.2023 · AE531114
Imagine you have a map with various paths and you need to find the shortest way to a treasure. Each path has its own rules, like how much weight you can carry or how fast you can travel. The Simplex algorithm helps you navigate these paths and rules to find the most efficient route to the treasure.

In technical terms, it deals with equations representing constraints (like the rules of each path) and a goal (like reaching the treasure in the shortest time). The algorithm iteratively explores vertices on a multidimensional shape (the map), checking at each step if it's closer to the best solution. It's like checking each intersection on a map to see if you're closer to the treasure. This continues until it finds the most efficient route, giving you the best solution to your problem.

Fossil-Free Frontier

14.11.2023 · AE531114
This project’s main goal is a linear programming model that re-envisions ambitious yet feasible renewable energy goals for key regions by focusing on the trade-offs between different fossil-free energy sources.  For this, the project focuses on the data of four common fossil-free energy sources: wind, solar, nuclear and hydro, as well as relevant variables such as Cost, Reliability, Existing Energy Mix and Public Approval.

Summary

14.11.2023 · AE531114

Focus: LP deals specifically with linear equations and inequalities. This means it works with problems where relationships are represented as straight lines (hence 'linear').

Objective: It always aims to find the maximum or minimum value of a linear equation, known as the objective function. For example, maximizing profit or minimizing cost.

Method: LP uses specific mathematical methods, like the Simplex algorithm, to find the best solution.

Constraints: All constraints in LP are linear (straight-line relationships). For instance, you can't spend more than a certain budget, or you need at least a certain amount of some ingredient.

Solutions: Solutions in LP are often numerical and can include fractions or decimals.

Trial and Error

17.10.2023 · AE531017
Trial and Error

Memory

28.11.2023 · AE531128

Imitation

28.11.2023 · AE531128

Swarm intelligence

28.11.2023 · AE531128

Repetition

17.10.2023 · AE531017
Repetition

Tangle v0.0.1 Optimization

14.11.2023 · AE531114
Here is a CSV containing information about nutritive values of different vegetables growable in a German garden, last column also contains expected yield per square meter. Please provide a combination of vegetables which would satisfy nutritive need of an adult man so that the surface on which the vegetables grow is minimized. To have the meal diversified, there should be not more than 300g of certain vegetable.

Game & Playfulness

17.10.2023 · AE531017
Game & Playfulness

Curiosity

17.10.2023 · AE531017
Curiosity

Intuition

17.10.2023 · AE531017
Intuition

Diet Problem

14.11.2023 · AE531114
Diet Problem (DP) involves finding the most cost-effective diet that meets all nutritional requirements. Imagine you have a list of foods, each with its own nutritional content and cost. Your goal is to choose a combination of these foods that provides all the necessary nutrients (like vitamins, proteins, carbohydrates, etc.) for the least possible cost. You set up equations for each nutrient, ensuring your diet doesn't fall short or exceed what's needed. Then, you use linear programming to minimize the total cost while satisfying these nutritional constraints. It's like solving a puzzle where you balance your health needs against your budget, finding the best possible dietary plan.

Constraint Programming Summary

14.11.2023 · AE531114

Focus: CP is more general and can handle a wide variety of constraints, not just linear ones. It can deal with logical conditions, like "either-or" situations, and can include non-linear relationships.

Objective: CP doesn't necessarily have an objective function to optimize. Instead, it focuses on finding solutions that satisfy all the given constraints.

Method: It uses different algorithms than LP, often based on search techniques, like backtracking or heuristics.

Constraints: Constraints in CP can be diverse - linear, non-linear, logical conditions, etc. For example, a constraint could be that a certain task must be done before another can start.

Solutions: Solutions in CP are often discrete (like whole numbers) and can involve deciding between different options or scenarios.

Multi-objective Optimization

29.10.2023 · AE531029
In multi-objective optimization, optimize for two or more objectives in the same time.