Friday, December 1, 2023

A Slime Mold Algorithm for Repairing a Power Transmission Network after an Electromagnetic Pulse Attack


After an extensive journey of in-depth exploration, spanning literature review, hypothesis formulation, modeling, implementation, and many weeks of simulation, Kristina Wogatai proudly presented her paper, "A Graph-Based Approach for Applying Biologically-Inspired Slime Mold Algorithms for Repairing a Power Transmission Network after an Electromagnetic Pulse Attack," at the 2nd International Conference on Power Systems and Electrical Technology (PSET) in Milan, Italy, held from August 25th to 27th, 2023. The paper, authored by Kristina Wogatai, Johannes Winkler, and Wilfried Elmenreich, explores how to apply slime mold algorithms to restore power grids after an electromagnetic pulse (EMP) attack.

Our proposed method intricately utilized a simulated slime mold algorithm on graph models to pinpoint critical repair areas, drawing inspiration from how slime molds construct networks between food sources. These single-celled organisms, known for their intelligent swarm behavior, have inspired algorithms addressing optimization problems and the creation of efficient transportation networks. Our open-source algorithm, SISMO (Simulation of Slime Molds), has contributed to this work.

Adapting the SISMO algorithm for connecting power stations and plants required overcoming challenges, such as incorporating geographic or demographic criteria for power line placement. Initially provided only with the positions of power stations, we addressed this problem by leveraging graph visualization algorithms like Force Atlas, Force Atlas2, and Yifan-Hu to modify the layout and thus communicate these parameters to the algorithm effectively.


Our efforts did not go unnoticed, as Kristina received the Best Oral Presentation Award at the conference, emphasizing the paper's quality and the significance of its findings in power network restoration.

For further information, check out the paper

Kristina Wogatai, Johannes Winkler, and Wilfried Elmenreich. A Graph-Based Approach for Applying Biologically-Inspired Slime Mold Algorithms for Repairing a Power Transmission Network after an Electromagnetic Pulse Attack. In Proc. 2023 2nd International Conference on Power Systems and Electrical Technology (PSET 2023), Milan, Italy, August 25-27, 2023.

Tuesday, May 9, 2023

Bottom-Up Bio-Inspired Algorithms for Optimizing Industrial Plants

Scheduling in a production plant with a high product diversity is an NP-hard problem. In large plants, traditional optimization methods reach their limits regarding computational time. In this paper, we use inspiration from two bio-inspired optimization algorithms, namely, the artificial bee colony (ABC) algorithm and the bat algorithm, and apply them to the job shop scheduling problem. Unlike previous work using these algorithms for global optimization, we do not apply them to solutions in the solution space, though, but rather choose a bottom-up approach and apply them as literal swarm intelligence algorithms. We use the example of a semiconductor production plant and map the bees and bats to actual entities in the plant (lots, machines) using agent-based modeling using the NetLogo simulation platform. These agents then interact with each other and the environment using local rules from which the global behavior – the optimization of the industrial plant – emerges. We measure performance compared to a baseline algorithm using engineered heuristics (FIFO, fill fullest batches first). Our results show that these types of algorithms, employed bottom-up, show promise of performance improvements using only low-effort local calculations.

Our newest research paper builds upon the simulation framework presented in http://demesos.blogspot.com/2022/08/swarmfabsim-simulation-framework-for.html

Asking Question at ICAART Panel Session
As in this earlier paper, algorithm performance was compared against a reference baseline algorithm using the key performance indicators of makespan, flow factor, delay, and machine utilization. Results show that using these swarm intelligence algorithms in a bottom-up manner with only low-effort local calculations can lead to performance improvements. The paper details the application of two algorithms to factory optimization, an artificial bee algorithm (ABC) and a bat-inspired algorithm. Both algorithms are used in a bottom-up approach, not as a global optimizer. In this type of approach, the swarm members do not represent solutions in the solution space of the problem but actual lots and/or machines in the factory. In conclusion, swarm intelligence algorithms can be a powerful tool for production plant scheduling optimization. Although the case study is based on a semiconductor production plant, the same approach applies well to other production plants as well.

Paper presentation at ICAART'23
Further information can be found in the paper

M. Umlauft, M. Gojkovic, K. Harshina and M. Schranz: Bottom-Up Bio-Inspired Algorithms for Optimizing Industrial Plants, Proceedings of ICAART 2023, ISBN: 978-989-758-623-1, doi:10.5220/0011693400003393

Wednesday, April 5, 2023

They say the best way to learn is by doing, but sometimes the best way is to automate!

Ah, the version control system git. We've all been there, typing out commands to push a new commit to the server, trying to remember which is which. For example to update the remote repository with your local changes, I use the git pull, add, commit and push commands in sequence. This will ensure that the remote repository is up-to-date with the local repository. Well, I had enough of it. I decided to take matters into my own hands and wrote a script that I named 'gits'. It's just a one-liner that does the steps of git pull, git add, git commit and git push for me, without all the hassle of having to type each paticular command. The commit message is given as argument to gits, if I forget about it, the script puts the number of changed files there as a placeholder.

@echo off
:: Batch script to commit and push your git changes
:: and quickly resolve conflicts
::
:: by Wil
:: March 2023 V0.21
::
:: The script has the decency to ask before adding new files
:: If an argument is given, this is used as the commit message
:: otherwise a generic commit message is generated

setlocal ENABLEDELAYEDEXPANSION

for /F "delims=#" %%E in ('"prompt #$E# & for %%E in (1) do rem "') do set "ESCchar=%%E"
set "red=%ESCchar%[91m"
set "green=%ESCchar%[92m"
set "yellow=%ESCchar%[93m"
set "magenta=%ESCchar%[95m"
set "cyan=%ESCchar%[96m"
set "white=%ESCchar%[97m"
set "black=%ESCchar%[30m"
set "nocolor=%ESCchar%[0m"
set "bold=%ESCchar%[1m"

::stage modifications and deletions
set countmodified=0
for /f %%C in ('git ls-files -m') do set /A countmodified=!countmodified!+1

if NOT "!countmodified!"=="0" (
  git add -u
)

set /A total=!countmodified!

for /f %%C in ('git diff --cached --numstat') do set /A total=!total!+1

::check if there are untracked (new) files
set countnew=0
for /f %%C in ('git ls-files . --exclude-standard --others') do set /A countnew=!countnew!+1

if NOT "!countnew!"=="0" (
  git ls-files . --exclude-standard --others
  echo.
  echo There are !countnew! files, should they be added?
  CHOICE /C asx /M "Press [A] for adding the files, [S] for skipping without and [X] for exiting this script."
  IF !ERRORLEVEL! EQU 3 (
    exit /b
  )
  IF !ERRORLEVEL! EQU 1 (
    git add .
    set /A total=!total!+!countnew!
  )
)

if "!total!"=="0" (
  echo Nothing to do!
) else (
  if "%1"=="" (
    git commit -m "updated !total! files"
  ) else (
    git commit -m "%*"
  )
  git pull
  git push

  set conflicts=0
  set unsolved=0
  for /f %%C in ('git ls-files -u  ^| cut -f 2  ^| sort ^|uniq') do (
    set cff=%%C
    call :SUBCHOICE
    IF !ERRORLEVEL! EQU 2 (
      git checkout --theirs !cff!
      git add !cff!
    ) ELSE IF !ERRORLEVEL! EQU 3 (
      git checkout --ours !cff!
      git add !cff!
    ) ELSE IF !ERRORLEVEL! EQU 4 (
      set /A unsolved=!unsolved!+1
    ) ELSE IF !ERRORLEVEL! EQU 5 (
      exit /b
    )
    set /A conflicts=!conflicts!+1
  )

  if !unsolved! GTR 0 (
    echo There are still %red%!conflicts! files%nocolor% in conflict.
    exit /b
  )
 
  if !conflicts! GTR 0 (
    git commit -m "merged conflicted files"
    git push
  )
)

exit /b

:SUBCHOICE
echo|set /p="File %red%!cff!%nocolor% is in conflict "
CHOICE /C dtosx /M "(show [D]iff, use [T]heirs, use [O]urs, [S]kip file, e[X]it script)"
   IF !ERRORLEVEL! EQU 1 (
      git diff !cff!
      goto SUBCHOICE
    )
   exit /B !ERRORLEVEL!

The Windows .bat code is a script for committing and pushing git changes, with the ability to quickly resolve conflicts. It sets up some color codes for the text output and checks for modifications, deletions, and untracked (new) files. It then adds the files to be committed and either uses an argument given to the script as the commit message, or a generic commit message. It then pulls, pushes, and checks for conflicts. If conflicts are present, it provides the user with the option to view a diff, select a version of the file, skip the file, or exit the script. If conflicts are resolved, the script commits the merged files and pushes them.

gits in action. Here it found files not added to the repo yet and proposes to add them, to do the commit without adding them or to stop the script

 

Thursday, March 9, 2023

Discovering New Ways to Navigate: A Swarm Intelligence-Based Robotic Search Algorithm Integrated with Game Theory

Robotics has come a long way in the last few decades, and we continue to see innovations in the field as researchers seek to improve robotic search algorithms. Recently, researchers have proposed a decentralize and asynchronous swarm robotic search algorithm integrated with game theory to better disperse robots in the environment while crossing obstacles and solving mazes. This prevents early convergence and improves the efficiency of the searches.

In the proposed algorithm, individual robots, while searching, play a sequential game at each iteration, and based on that, choose their velocity update rule. This strategic game works well in search environments with different levels of complexity and especially improves search efficiency further in complex environments. In the target problem, since the environment is unknown, it is not possible to preplan a path to the target. And there is no difference between static and dynamic obstacles, as the robots cannot distinguish them. Thus, in the proposed method, passing and avoiding obstacles are synchronized with the target searching.

Example of a maze-like complex environment and its mapping to a fitness function

The simulation results showed that, following the proposed algorithm, robots disperse well in search environments, and therefore search speed increases by up to 24% and attended path length to target lessens by up to 23.5% in complex search environments. Also, the proposed algorithm has a success rate equal to the state-of-the-art, which is 100% in all of the tested environments.

For more details check out the paper:

Khalil Alrahman Youssefi Darmian, Modjtaba Rouhani, Habib Rajabi Mashhadi, and Wilfried Elmenreich. A swarm intelligence-based robotic search algorithm integrated with game theory. Applied Soft Computing, 122, 4 2022. (doi:10.1016/j.asoc.2022.108873)

Robotics is an exciting and ever-evolving field, and this new algorithm shows us the potential of swarm intelligence-based robotic search algorithms. We look forward to seeing more innovations in this area as researchers continue to explore new ways to navigate.

Tuesday, August 2, 2022

SwarmFabSim: A simulation framework for bottom-up optimization in flexible job-shop scheduling using Netlogo

It was great to be in presence at a conference again. At the 12th International Conference on Simulation and Modeling Methodologies, Technologies and Applications, aka SIMULTECH, we presented our paper 

Martina Umlauft, Melanie Schranz, and Wilfried Elmenreich. SwarmFabSim: A simulation framework for bottom-up optimization in flexible job-shop scheduling using Netlogo. In Proceedings of the 12th International Conference on Simulation and Modeling Methodologies, Technologies and Applications - SIMULTECH. SciTePress, July 2022. (doi:10.5220/0011274700003274

Click triangle for Bibtex entry
@inproceedings{umlauft:swarmfabsim:22,
  author = {Umlauft, Martina and Schranz, Melanie and Elmenreich, Wilfried},
  title = {{SwarmFabSim}: {A} Simulation Framework for Bottom-up Optimization
in Flexible Job-Shop Scheduling Using {N}etLogo},
  booktitle = {Proceedings of the 12th International Conference on Simulation and Modeling Methodologies, Technologies and Applications - SIMULTECH},
  year = {2022},
  month = jul,
  publisher = {SciTePress},
  doi = {10.5220/0011274700003274},
}
  

The paper shows how to the programming language NetLogo to model and simulate a factory producing according to the job-shop manufacturing principle. The main contribution is a modular simulation framework that can apply various algorithms to optimize a make-to-order manufacturing system and supports multiple configurable scenarios. The evaluation framework was used to assess the effectiveness of an artificial hormone algorithm compared to a naïve basic implementation and a reference baseline algorithm. The evaluation was based on three key performance indicators: Flow factor, delay, and utilization. The simulations show promising results of the artificial hormone algorithm in three reference scenarios with significant improvements over the reference algorithms. The implementation of the simulation environment is published as open source in the Git repository https://swarmfabsim.github.io. Readers are welcome to contribute with their ideas and developments.

Screenshot of the SwarmFabSim application

Tuesday, February 9, 2021

An Artificial Hormone-based Algorithm for Production Scheduling

Artificial hormone systems are inspired by the natural endocrine system that adjusts the metabolism of tissue cells in our body. By connecting decisions and actions in a system to the production and evaporation of artificial hormones, it is possible to create a bio-inspired self-organizing algorithm.

Application areas for such algorithms are problems with many agents to be coordinated, where existing optimization approaches come to their limit. An example of such a problem is the production of logic and power integrated circuits (ICs) in the semiconductor industry. Unlike the high-volume production of memory ICs, wafer production in the logic and power sector has a large product mix. This involves many processing steps and dynamic changes of involved machines.

Weekly workloads can involve around 100 000 operations on thousands of machines. Optimizing such a system for work in progress and flow factor is an NP-hard problem. At this size, existing dispatching rules and linear optimization methods cannot cope with the NP-hard search space, thus not optimize the entire system.

To address this issue, we have modeled a production plant as a self-organizing system of agents that interact with each other in a non-linear way. As it is common in the semiconductor industry, wafers are combined in groups of 25 pieces forming a so-called lot. In our approach, an artificial hormone systems is used to express a lot's urgency and the need for new lots at a machine type, thus providing a system using local information for optimization. The algorithm builds upon five principles, which are 

  • (i) machines produce hormone to attract lots, 
  • (ii) hormone diffuses process-upstream, 
  • (iii) incoming lots diffuse hormone, 
  • (iv) lots are prioritized by their timing, and 
  • (v) lots are attracted by hormone. 

Via these mechanisms, machines can balance their workload by pulling required lots towards them. The algorithm has been implemented and evaluated in a NetLogo simulation model. Simulation results indicate that the artificial hormone system improves around 5% for overall production time and flow factor compared to a baseline algorithm. Future work will investigate if the hormone algorithm can be used on top of existing production systems. In a productive system an improvement of 5% would be highly notable.

More information can be found on the SWILT project webpage and in the paper

Wilfried Elmenreich, Alexander Schnabl, and Melanie Schranz. An artificial hormone-based algorithm for productionscheduling from the bottom-up. In Proceedings of the 13th International Conference on Agents and Artificial Intelligence. SciTePress, February 2021.

Click triangle for Bibtex entry
@inproceedings{elmenreich:Hormone:21,
  author = {Elmenreich, Wilfried and Schnabl, 
    Alexander and Schranz, Melanie},
  title = {An artificial hormone-based algorithm
    for production scheduling from the bottom-up},
  booktitle = {Proceedings of the 13th International 
    Conference on Agents and Artificial Intelligence},
  year = {2021},
  month = feb,
  publisher = {SciTePress}
}  
  

Wednesday, November 11, 2020

Benford’s Law and the US 2020 Presidential Election Votes

Benford’s law states that if you get a big range of data from the real world and you look at the lead digit of each of the values you get significantly more 1s than other digits if the numbers span multiple magnitudes.

As one application, Benford’s law is used to detect fraud in accounting. There typically, the pairs of the two first digits are analyzed and plotted according to their frequency in order to detect anomalies. An anomaly can have different explanations though.

For example, in the US 2020 presidential elections, the proportion of digits 1 and 2 on first digits for votes for Mr. Biden is lower than expected, while for votes for Mr. Trump the proportion of digits 1 and 2 on first digits is slightly higher.


In the video below, Matt Parker analyzes the situation and shows that the more densely populated areas in the US, where a majority of Mr. Biden's votes are coming from, have precincts with mostly the same size. Thus here the condition of having data spanning multiple magnitudes is not fulfilled, hence we get a distribution of first digits that deviates from the prediction by Benford’s law.

When looking at the frequency of the last digits, there is an anomaly in the voter data for Mr. Trump. Instead of having a roughly equal distribution of frequency of last digits, the lower digits are much higher. This is due to the fact that a majority of votes for Mr. Trump come from smaller precincts thus favoring the smaller numbers.

 

Thus, the deviation of voting counts (from precincts with a standardized size) from Benford’s Law is not an indicaton of voter fraud but rather a phenomenon to be expected.

Further reading:
Deckert, J., Myagkov, M., & Ordeshook, P. (2011). Benford's Law and the Detection of Election Fraud. Political Analysis, 19(3), 245-268. doi:10.1093/pan/mpr014