Code and data repository for the paper titled as "Incorporating Sub-programs as Knowledge in Program Synthesis by PushGP and Adaptive Replacement Mutation"
Table of Contents
Genetic programming (GP) searches a program by random initialization, unguided variation, and fitness-guided selection. This shows a difference to a human programmer. Usually, a human programmer writes code based on his knowledge from his previous programming experience.
This study aims to build a system so that GP could use the knowledge from the previous problems it solved in a sequence of problem-solving (shown in the above figure). We use sub-programs as knowledge in the current study.
Click here to see a detailed description of knowledge.
Details
The flowchart above shows a simple version of our framework of the Knowledge-Driven Program Synthesis (KDPS) system. It works as follows.
- The system saves knowledge from the program generated by GP to an Offline Knowledge Archive (Offline KA).
- The system creates an Online Knowledge Archive (Online KA) from the Offline KA.
- The system selects knowledge from the Online KA to the GP.
- The system evaluates the knowledge based on the feedback from GP.
A more detailed design of our conceptual system is in Detailed design of the conceptual system.
Details
In the current study, we ommit the Offline KA and focus on the implementation of Online KA as the first step. Therefore, the steps related to Offline KA are replaced by Human.
-
Install Python 3 (< 3.10) on your computer
-
Install required libraries
pip install numpy pyyaml
-
Clone the entire repository
git clone https://github.com/Y1fanHE/pushgp-adaptive-replacement-\ mutation-with-knowledge.git
-
Install the modified PyshGP with the following commands
cd pyshgp pip install .
-
Download data files of the benchmark problems and expand the archive
tar zxvf psgb.tgz
This command should create a folder named
psgb
including data files of the four problems at the root of this repository. -
Test your installation
python 02/umad.py 1000
The above command runs PushGP with UMAD to solve the Small or Large problem with seed 1000.
First, copy the Shell scripts in shell_script
folder to the
repository root
cp shell_script/* .
In the paper, we totally performed the following experiments. We list them with the command to run these experiments.
-
Experiment I: adaptive replacement mutation under an ideal condition
-
Prepare the knowledge archives & Effectiveness of the adaptive replacement mutation
./exp102.sh && ./exp104.sh && ./exp114.sh && ./exp127.sh
-
Robustness of the adaptive replacement mutation
./exp202.sh && ./exp204.sh && ./exp214.sh && ./exp227.sh
-
Tracking the tested-good knowledge
./exp302.sh && ./exp304.sh && ./exp314.sh && ./exp327.sh
-
-
Experiment II: adaptive replacement mutation under a realistic condition
./exp402.sh && ./exp404.sh && ./exp414.sh && ./exp427.sh ./expc01.sh && ./expc02.sh
-
The raw data of the experiments is stored in the
02/dat
,04/dat
,14/dat
,27/dat
,c01/dat
, andc02/dat
folders. -
Copy the Jupyter notebooks in the folder
notebook
to the repository root.cp notebook/* .
Now, you can also check the results with exp1.ipynb, exp2.ipynb, exp3.ipynb, and exp4.ipynb.
-
The figures used in the manuscript are generated by the Jupyter Notebooks and move to the
fig
folder by the following command../rename_img.sh
- The success rate of five methods on four benchmark problems in Experiment I
This section describes the detailed design of our conceptual system in four parts, namely GP & Online KA, GP & Offline KA, Online KA & Offline KA, and Offline KA.
Details
- The Selector selects knowledge from the Online KA. This knowledge could be mutated by the Mutator.
- The Extractor extracts knowledge during the optimization of GP.
- The GP returns the knowledge applied into the search process before.
- The Evaluator evaluates the quality of the knowledge, either extractrd or returned directly from GP, based on the evolutionary process.
- The Online KA collects the evaluated knowledge to update the unevaluated ones
Details
- The Extractor extracts knowledge from the program generated by GP.
- The Offline KA collectes the extracted knowledge.
Details
editing ...
Details
editing ...
Distributed under the MIT License. See LICENSE
for more information.
- Yifan He (he.yifan.xs@alumni.tsukuba.ac.jp)
- Claus Aranha (caranha@cs.tsukuba.ac.jp)
Our implementation is based on PyshGP. We are grateful to @erp12 for his effort on developing this library.
The data files of the benchmark problems are from an GitHub repository. We express our thanks to @thelmuth for this wonderful sharing.