added
LICENSE
|
|
@@ -0,0 +1,201 @@
|
|
1
|
+ Apache License
|
|
2
|
+ Version 2.0, January 2004
|
|
3
|
+ https://www.apache.org/licenses/
|
|
4
|
+
|
|
5
|
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
|
|
6
|
+
|
|
7
|
+ 1. Definitions.
|
|
8
|
+
|
|
9
|
+ "License" shall mean the terms and conditions for use, reproduction,
|
|
10
|
+ and distribution as defined by Sections 1 through 9 of this document.
|
|
11
|
+
|
|
12
|
+ "Licensor" shall mean the copyright owner or entity authorized by
|
|
13
|
+ the copyright owner that is granting the License.
|
|
14
|
+
|
|
15
|
+ "Legal Entity" shall mean the union of the acting entity and all
|
|
16
|
+ other entities that control, are controlled by, or are under common
|
|
17
|
+ control with that entity. For the purposes of this definition,
|
|
18
|
+ "control" means (i) the power, direct or indirect, to cause the
|
|
19
|
+ direction or management of such entity, whether by contract or
|
|
20
|
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
|
|
21
|
+ outstanding shares, or (iii) beneficial ownership of such entity.
|
|
22
|
+
|
|
23
|
+ "You" (or "Your") shall mean an individual or Legal Entity
|
|
24
|
+ exercising permissions granted by this License.
|
|
25
|
+
|
|
26
|
+ "Source" form shall mean the preferred form for making modifications,
|
|
27
|
+ including but not limited to software source code, documentation
|
|
28
|
+ source, and configuration files.
|
|
29
|
+
|
|
30
|
+ "Object" form shall mean any form resulting from mechanical
|
|
31
|
+ transformation or translation of a Source form, including but
|
|
32
|
+ not limited to compiled object code, generated documentation,
|
|
33
|
+ and conversions to other media types.
|
|
34
|
+
|
|
35
|
+ "Work" shall mean the work of authorship, whether in Source or
|
|
36
|
+ Object form, made available under the License, as indicated by a
|
|
37
|
+ copyright notice that is included in or attached to the work
|
|
38
|
+ (an example is provided in the Appendix below).
|
|
39
|
+
|
|
40
|
+ "Derivative Works" shall mean any work, whether in Source or Object
|
|
41
|
+ form, that is based on (or derived from) the Work and for which the
|
|
42
|
+ editorial revisions, annotations, elaborations, or other modifications
|
|
43
|
+ represent, as a whole, an original work of authorship. For the purposes
|
|
44
|
+ of this License, Derivative Works shall not include works that remain
|
|
45
|
+ separable from, or merely link (or bind by name) to the interfaces of,
|
|
46
|
+ the Work and Derivative Works thereof.
|
|
47
|
+
|
|
48
|
+ "Contribution" shall mean any work of authorship, including
|
|
49
|
+ the original version of the Work and any modifications or additions
|
|
50
|
+ to that Work or Derivative Works thereof, that is intentionally
|
|
51
|
+ submitted to Licensor for inclusion in the Work by the copyright owner
|
|
52
|
+ or by an individual or Legal Entity authorized to submit on behalf of
|
|
53
|
+ the copyright owner. For the purposes of this definition, "submitted"
|
|
54
|
+ means any form of electronic, verbal, or written communication sent
|
|
55
|
+ to the Licensor or its representatives, including but not limited to
|
|
56
|
+ communication on electronic mailing lists, source code control systems,
|
|
57
|
+ and issue tracking systems that are managed by, or on behalf of, the
|
|
58
|
+ Licensor for the purpose of discussing and improving the Work, but
|
|
59
|
+ excluding communication that is conspicuously marked or otherwise
|
|
60
|
+ designated in writing by the copyright owner as "Not a Contribution."
|
|
61
|
+
|
|
62
|
+ "Contributor" shall mean Licensor and any individual or Legal Entity
|
|
63
|
+ on behalf of whom a Contribution has been received by Licensor and
|
|
64
|
+ subsequently incorporated within the Work.
|
|
65
|
+
|
|
66
|
+ 2. Grant of Copyright License. Subject to the terms and conditions of
|
|
67
|
+ this License, each Contributor hereby grants to You a perpetual,
|
|
68
|
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
|
|
69
|
+ copyright license to reproduce, prepare Derivative Works of,
|
|
70
|
+ publicly display, publicly perform, sublicense, and distribute the
|
|
71
|
+ Work and such Derivative Works in Source or Object form.
|
|
72
|
+
|
|
73
|
+ 3. Grant of Patent License. Subject to the terms and conditions of
|
|
74
|
+ this License, each Contributor hereby grants to You a perpetual,
|
|
75
|
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
|
|
76
|
+ (except as stated in this section) patent license to make, have made,
|
|
77
|
+ use, offer to sell, sell, import, and otherwise transfer the Work,
|
|
78
|
+ where such license applies only to those patent claims licensable
|
|
79
|
+ by such Contributor that are necessarily infringed by their
|
|
80
|
+ Contribution(s) alone or by combination of their Contribution(s)
|
|
81
|
+ with the Work to which such Contribution(s) was submitted. If You
|
|
82
|
+ institute patent litigation against any entity (including a
|
|
83
|
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
|
|
84
|
+ or a Contribution incorporated within the Work constitutes direct
|
|
85
|
+ or contributory patent infringement, then any patent licenses
|
|
86
|
+ granted to You under this License for that Work shall terminate
|
|
87
|
+ as of the date such litigation is filed.
|
|
88
|
+
|
|
89
|
+ 4. Redistribution. You may reproduce and distribute copies of the
|
|
90
|
+ Work or Derivative Works thereof in any medium, with or without
|
|
91
|
+ modifications, and in Source or Object form, provided that You
|
|
92
|
+ meet the following conditions:
|
|
93
|
+
|
|
94
|
+ (a) You must give any other recipients of the Work or
|
|
95
|
+ Derivative Works a copy of this License; and
|
|
96
|
+
|
|
97
|
+ (b) You must cause any modified files to carry prominent notices
|
|
98
|
+ stating that You changed the files; and
|
|
99
|
+
|
|
100
|
+ (c) You must retain, in the Source form of any Derivative Works
|
|
101
|
+ that You distribute, all copyright, patent, trademark, and
|
|
102
|
+ attribution notices from the Source form of the Work,
|
|
103
|
+ excluding those notices that do not pertain to any part of
|
|
104
|
+ the Derivative Works; and
|
|
105
|
+
|
|
106
|
+ (d) If the Work includes a "NOTICE" text file as part of its
|
|
107
|
+ distribution, then any Derivative Works that You distribute must
|
|
108
|
+ include a readable copy of the attribution notices contained
|
|
109
|
+ within such NOTICE file, excluding those notices that do not
|
|
110
|
+ pertain to any part of the Derivative Works, in at least one
|
|
111
|
+ of the following places: within a NOTICE text file distributed
|
|
112
|
+ as part of the Derivative Works; within the Source form or
|
|
113
|
+ documentation, if provided along with the Derivative Works; or,
|
|
114
|
+ within a display generated by the Derivative Works, if and
|
|
115
|
+ wherever such third-party notices normally appear. The contents
|
|
116
|
+ of the NOTICE file are for informational purposes only and
|
|
117
|
+ do not modify the License. You may add Your own attribution
|
|
118
|
+ notices within Derivative Works that You distribute, alongside
|
|
119
|
+ or as an addendum to the NOTICE text from the Work, provided
|
|
120
|
+ that such additional attribution notices cannot be construed
|
|
121
|
+ as modifying the License.
|
|
122
|
+
|
|
123
|
+ You may add Your own copyright statement to Your modifications and
|
|
124
|
+ may provide additional or different license terms and conditions
|
|
125
|
+ for use, reproduction, or distribution of Your modifications, or
|
|
126
|
+ for any such Derivative Works as a whole, provided Your use,
|
|
127
|
+ reproduction, and distribution of the Work otherwise complies with
|
|
128
|
+ the conditions stated in this License.
|
|
129
|
+
|
|
130
|
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
|
|
131
|
+ any Contribution intentionally submitted for inclusion in the Work
|
|
132
|
+ by You to the Licensor shall be under the terms and conditions of
|
|
133
|
+ this License, without any additional terms or conditions.
|
|
134
|
+ Notwithstanding the above, nothing herein shall supersede or modify
|
|
135
|
+ the terms of any separate license agreement you may have executed
|
|
136
|
+ with Licensor regarding such Contributions.
|
|
137
|
+
|
|
138
|
+ 6. Trademarks. This License does not grant permission to use the trade
|
|
139
|
+ names, trademarks, service marks, or product names of the Licensor,
|
|
140
|
+ except as required for reasonable and customary use in describing the
|
|
141
|
+ origin of the Work and reproducing the content of the NOTICE file.
|
|
142
|
+
|
|
143
|
+ 7. Disclaimer of Warranty. Unless required by applicable law or
|
|
144
|
+ agreed to in writing, Licensor provides the Work (and each
|
|
145
|
+ Contributor provides its Contributions) on an "AS IS" BASIS,
|
|
146
|
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
|
|
147
|
+ implied, including, without limitation, any warranties or conditions
|
|
148
|
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
|
|
149
|
+ PARTICULAR PURPOSE. You are solely responsible for determining the
|
|
150
|
+ appropriateness of using or redistributing the Work and assume any
|
|
151
|
+ risks associated with Your exercise of permissions under this License.
|
|
152
|
+
|
|
153
|
+ 8. Limitation of Liability. In no event and under no legal theory,
|
|
154
|
+ whether in tort (including negligence), contract, or otherwise,
|
|
155
|
+ unless required by applicable law (such as deliberate and grossly
|
|
156
|
+ negligent acts) or agreed to in writing, shall any Contributor be
|
|
157
|
+ liable to You for damages, including any direct, indirect, special,
|
|
158
|
+ incidental, or consequential damages of any character arising as a
|
|
159
|
+ result of this License or out of the use or inability to use the
|
|
160
|
+ Work (including but not limited to damages for loss of goodwill,
|
|
161
|
+ work stoppage, computer failure or malfunction, or any and all
|
|
162
|
+ other commercial damages or losses), even if such Contributor
|
|
163
|
+ has been advised of the possibility of such damages.
|
|
164
|
+
|
|
165
|
+ 9. Accepting Warranty or Additional Liability. While redistributing
|
|
166
|
+ the Work or Derivative Works thereof, You may choose to offer,
|
|
167
|
+ and charge a fee for, acceptance of support, warranty, indemnity,
|
|
168
|
+ or other liability obligations and/or rights consistent with this
|
|
169
|
+ License. However, in accepting such obligations, You may act only
|
|
170
|
+ on Your own behalf and on Your sole responsibility, not on behalf
|
|
171
|
+ of any other Contributor, and only if You agree to indemnify,
|
|
172
|
+ defend, and hold each Contributor harmless for any liability
|
|
173
|
+ incurred by, or claims asserted against, such Contributor by reason
|
|
174
|
+ of your accepting any such warranty or additional liability.
|
|
175
|
+
|
|
176
|
+ END OF TERMS AND CONDITIONS
|
|
177
|
+
|
|
178
|
+ APPENDIX: How to apply the Apache License to your work.
|
|
179
|
+
|
|
180
|
+ To apply the Apache License to your work, attach the following
|
|
181
|
+ boilerplate notice, with the fields enclosed by brackets "[]"
|
|
182
|
+ replaced with your own identifying information. (Don't include
|
|
183
|
+ the brackets!) The text should be enclosed in the appropriate
|
|
184
|
+ comment syntax for the file format. We also recommend that a
|
|
185
|
+ file or class name and description of purpose be included on the
|
|
186
|
+ same "printed page" as the copyright notice for easier
|
|
187
|
+ identification within third-party archives.
|
|
188
|
+
|
|
189
|
+ Copyright [yyyy] [name of copyright owner]
|
|
190
|
+
|
|
191
|
+ Licensed under the Apache License, Version 2.0 (the "License");
|
|
192
|
+ you may not use this file except in compliance with the License.
|
|
193
|
+ You may obtain a copy of the License at
|
|
194
|
+
|
|
195
|
+ https://www.apache.org/licenses/LICENSE-2.0
|
|
196
|
+
|
|
197
|
+ Unless required by applicable law or agreed to in writing, software
|
|
198
|
+ distributed under the License is distributed on an "AS IS" BASIS,
|
|
199
|
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
200
|
+ See the License for the specific language governing permissions and
|
|
201
|
+ limitations under the License.
|
changed
README.md
|
|
@@ -4,9 +4,14 @@
|
|
4
4
|
|
|
5
5
|
[](https://travis-ci.org/seanmor5/genex)
|
|
6
6
|
[](https://coveralls.io/github/seanmor5/genex?branch=master)
|
|
7
|
+ [](https://hex.pm/packages/genex/0.1.4)
|
|
7
8
|
|
|
8
9
|
This library is inspired by Python's [DEAP](https://github.com/deap/deap).
|
|
9
10
|
|
|
11
|
+ ## Documentation
|
|
12
|
+
|
|
13
|
+ Documentation is available at [https://hexdocs.pm/genex/introduction-overview.html](https://hexdocs.pm/genex/introduction-overview.html)
|
|
14
|
+
|
|
10
15
|
## Installation
|
|
11
16
|
|
|
12
17
|
The package can be installed by adding `genex` to your list of dependencies in `mix.exs`.
|
|
|
@@ -21,11 +26,7 @@ end
|
|
21
26
|
|
|
22
27
|
## Usage
|
|
23
28
|
|
|
24
|
- Genex works by making transformations on a `Population`.
|
|
25
|
-
|
|
26
|
- The simplest way to use Genex is by including it in one of your modules with default parameters.
|
|
27
|
-
|
|
28
|
- It requires you to implement 3 functions: `encoding/0`, `fitness_function/1`, `terminate?/1`.
|
|
29
|
+ Genex requires an implementation module with 3 functions: `encoding/0`, `fitness_function/1`, and `terminate?/1`.
|
|
29
30
|
|
|
30
31
|
```elixir
|
|
31
32
|
defmodule OneMax do
|
|
|
@@ -41,28 +42,42 @@ defmodule OneMax do
|
|
41
42
|
end
|
|
42
43
|
```
|
|
43
44
|
|
|
44
|
- Your algorithm can then be run by calling the `run/0` method Genex provides.
|
|
45
|
+ Now, run `iex -S mix`.
|
|
45
46
|
|
|
46
|
- ## Visualization
|
|
47
|
-
|
|
48
|
- Genex currently offers text visualization of populations. To view a summary of the solution your algorithm produced simply do:
|
|
49
|
- ```elixir
|
|
50
|
- soln = OneMax.run()
|
|
51
|
- Genex.Visualizers.Text.display_summary(soln)
|
|
47
|
+ Then:
|
|
48
|
+ ```
|
|
49
|
+ iex> OneMax.run()
|
|
52
50
|
```
|
|
53
51
|
|
|
54
|
- ## Genealogy
|
|
52
|
+ ## Features
|
|
55
53
|
|
|
56
|
- Genex comes with an implementation of a Genealogy tree using an Erlang digraph. The tree is available in the `history` field of the `Population` struct. As of this version of Genex, there are no pre-packaged genealogy visualizers. You'll have to find a third-party solution.
|
|
54
|
+ Genex strives to be as simple and customizable as possible. Along with the ability to customize EVERY step of your Genetic algorithm, Genex comes with the following features:
|
|
57
55
|
|
|
58
|
- ## Configuration
|
|
56
|
+ - 6 Selection Operators
|
|
57
|
+ - 7 Crossover Operators
|
|
58
|
+ - 6 Mutation Operators
|
|
59
|
+ - Customizable Population Statistics
|
|
60
|
+ - Customizable Benchmarking of Algorithms
|
|
61
|
+ - Exportable Genealogy Tree
|
|
62
|
+ - Flexible Encoding of Chromosomes
|
|
63
|
+ - Simple Text Visualizations
|
|
59
64
|
|
|
60
|
- Genex can be configured like so:
|
|
61
|
- ```elixir
|
|
62
|
- def MyGA do
|
|
63
|
- use Genex, crossover_type: :two_point, crossover_rate: 0.5
|
|
64
|
- ...
|
|
65
|
- end
|
|
65
|
+ ## Benchmarks
|
|
66
|
+
|
|
67
|
+ To run benchmarks, clone this repo. In the `genex` directory run:
|
|
68
|
+
|
|
69
|
+ ```
|
|
70
|
+ mix run bench/benchmarks.exs
|
|
66
71
|
```
|
|
67
72
|
|
|
68
|
- Please see the [documentation](https://hexdocs.pm/genex/tutorials-getting-started.html#content) for a full list of configuration options.
|
|
73
|
+ You can also run the individual benchmarks available in the `bench/` directory. This will take some time!
|
|
74
|
+
|
|
75
|
+ ## Contributing
|
|
76
|
+
|
|
77
|
+ If you have any problems with Genex, please open an issue! If you have a fix for an issue, submit a pull request.
|
|
78
|
+
|
|
79
|
+ ## Roadmap
|
|
80
|
+
|
|
81
|
+ The next phase of this library will involve extensive performance improvements. Most of the algorithms involve processing very large lists. This is an ideal job for a NIF.
|
|
82
|
+
|
|
83
|
+ If anybody has any experience writing NIFs or writing algorithms for processing large lists, [email me](mailto:[email protected]) to get involved!
|
|
|
\ No newline at end of file
|
changed
changelog.md
|
|
@@ -1,5 +1,18 @@
|
|
1
|
+ # v0.1.2
|
|
2
|
+ - Bug fixes
|
|
3
|
+ - Added population statistics
|
|
4
|
+ - Crossover rate and mutation rate implemented as functions
|
|
5
|
+
|
|
1
6
|
# v0.1.4
|
|
2
7
|
- Bug fixes
|
|
3
8
|
- 3.51x Performance Improvement in single_point crossover
|
|
4
9
|
- 2.35x Performance Improvement in two_point crossover
|
|
5
10
|
- Addition of `benchmark/0` function to benchmark your algorithm
|
|
11
|
+
|
|
12
|
+ # v0.2.0
|
|
13
|
+ - Changed to `libgraph` for Genealogy tree.
|
|
14
|
+ - Added ability to export graph as DOT file.
|
|
15
|
+ - Removed `track_history?` flag.
|
|
16
|
+ - Added 17 Tests, Plus Doctests
|
|
17
|
+ - Fixed Variance bug
|
|
18
|
+ - Added methods WITHOUT random variables to verify validity of operator algorithms.
|
|
|
\ No newline at end of file
|
changed
hex_metadata.config
|
|
@@ -11,7 +11,7 @@
|
|
11
11
|
<<"lib/genex/operators/selection.ex">>,
|
|
12
12
|
<<"lib/genex/operators/mutation.ex">>,<<"lib/genex/visualizers">>,
|
|
13
13
|
<<"lib/genex/visualizers/text.ex">>,<<"lib/genex.ex">>,<<".formatter.exs">>,
|
|
14
|
- <<"mix.exs">>,<<"README.md">>,<<"changelog.md">>]}.
|
|
14
|
+ <<"mix.exs">>,<<"README.md">>,<<"LICENSE">>,<<"changelog.md">>]}.
|
|
15
15
|
{<<"licenses">>,[<<"Apache-2.0">>]}.
|
|
16
16
|
{<<"links">>,[{<<"GitHub">>,<<"https://www.github.com/seanmor5/genex">>}]}.
|
|
17
17
|
{<<"name">>,<<"genex">>}.
|
|
|
@@ -25,5 +25,10 @@
|
|
25
25
|
{<<"name">>,<<"benchee">>},
|
|
26
26
|
{<<"optional">>,false},
|
|
27
27
|
{<<"repository">>,<<"hexpm">>},
|
|
28
|
- {<<"requirement">>,<<"~> 1.0">>}]]}.
|
|
29
|
- {<<"version">>,<<"0.1.4">>}.
|
|
28
|
+ {<<"requirement">>,<<"~> 1.0">>}],
|
|
29
|
+ [{<<"app">>,<<"libgraph">>},
|
|
30
|
+ {<<"name">>,<<"libgraph">>},
|
|
31
|
+ {<<"optional">>,false},
|
|
32
|
+ {<<"repository">>,<<"hexpm">>},
|
|
33
|
+ {<<"requirement">>,<<"~> 0.13.0">>}]]}.
|
|
34
|
+ {<<"version">>,<<"0.2.0">>}.
|
changed
lib/genex.ex
|
|
@@ -14,18 +14,20 @@ defmodule Genex do
|
|
14
14
|
Genex is a simple library for creating Genetic Algorithms in Elixir. A Genetic Algorithm is a search-based optimization technique based on the principles of Genetics and Natural Selection.
|
|
15
15
|
|
|
16
16
|
The basic life-cycle of a Genetic Algorithm is as follows:
|
|
17
|
- 1) Initialize the Population
|
|
18
|
- 2) Loop until goal is reached
|
|
19
|
- a) Select Parents
|
|
20
|
- b) Perform Crossover
|
|
21
|
- c) Mutate some of population
|
|
22
|
- d) Select Survivors
|
|
23
17
|
|
|
24
|
- Genex follows a structure similar to the one above and offers callbacks corresponding to each stage in the genetic algorithm to allow for full customization.
|
|
18
|
+ 1) Initialize the Population
|
|
19
|
+ 2) Loop until goal is reached
|
|
20
|
+ a) Select Parents
|
|
21
|
+ b) Perform Crossover
|
|
22
|
+ c) Mutate some of population
|
|
23
|
+ d) Select Survivors
|
|
25
24
|
|
|
26
|
- # Implementation
|
|
25
|
+ Genex uses a structure similar to the one above, using callbacks to give you full control over your genetic algorithm.
|
|
26
|
+
|
|
27
|
+ ## Implementation
|
|
27
28
|
|
|
28
29
|
Genex requires an implementation module:
|
|
30
|
+
|
|
29
31
|
```
|
|
30
32
|
defmodule OneMax do
|
|
31
33
|
use Genex
|
|
|
@@ -39,9 +41,10 @@ defmodule Genex do
|
|
39
41
|
def terminate?(population), do: population.max_fitness == 15
|
|
40
42
|
end
|
|
41
43
|
```
|
|
44
|
+
|
|
42
45
|
Genex requires 3 function definitions: `encoding/0`, `fitness_function/1`, and `terminate?/1`. Let's take a closer look at each of these:
|
|
43
46
|
|
|
44
|
- ## Encoding
|
|
47
|
+ ### Encoding
|
|
45
48
|
```
|
|
46
49
|
def encoding do
|
|
47
50
|
for _ <- 1..15, do: Enum.random(0..1)
|
|
|
@@ -50,7 +53,7 @@ defmodule Genex do
|
|
50
53
|
|
|
51
54
|
`encoding/0` defines your encoding of the chromosome's genes for your use-case. In the example above, we define a Binary Gene Set of length 15. Genex uses this function to generate an initial population of Chromosomes matching your encoding.
|
|
52
55
|
|
|
53
|
- ## Fitness Function
|
|
56
|
+ ### Fitness Function
|
|
54
57
|
```
|
|
55
58
|
def fitness_function(chromosome) do
|
|
56
59
|
Enum.sum(chromosome.genes)
|
|
|
@@ -59,7 +62,7 @@ defmodule Genex do
|
|
59
62
|
|
|
60
63
|
`fitness_function/1` defines how the algorithm evaluates the fitness of a chromosome. It takes in a chromosome struct and returns a number. Fitness is how your algorithm determines which chromosomes should be persisted to the next generation as well as which chromosomes should be selected to crossover. In this case, we want to maximize 1's in our set of genes, so we define fitness as the sum of genes.
|
|
61
64
|
|
|
62
|
- ## Termination Criteria
|
|
65
|
+ ### Termination Criteria
|
|
63
66
|
```
|
|
64
67
|
def terminate?(population) do
|
|
65
68
|
population.max_fitness == 15
|
|
|
@@ -68,7 +71,7 @@ defmodule Genex do
|
|
68
71
|
|
|
69
72
|
`terminate?/1` defines the termination criteria for your algorithm. This tells Genex when your algorithm should stop running. In this case we use a Max Fitness; however, you can also tell the algorithm to stop after a certain number of generations.
|
|
70
73
|
|
|
71
|
- # Running
|
|
74
|
+ ## Running
|
|
72
75
|
|
|
73
76
|
Once you have defined an implementation module. Utilize the `run/0` function to run the algorithm. The function will return the solution population for analysis. You can display a summary of the solution with the: `Genex.Visualizers.Text.display_summary/1` function.
|
|
74
77
|
|
|
|
@@ -77,39 +80,13 @@ defmodule Genex do
|
|
77
80
|
Genex.Visualizers.Text.display_summary(soln)
|
|
78
81
|
```
|
|
79
82
|
|
|
80
|
- # Configuration
|
|
83
|
+ ## Configuration
|
|
81
84
|
|
|
82
|
- Genex offers a number of settings to adjust the algorithm to your liking. You can adjust: strategies, rates, and more. Below is a comprehensive list of settings and options.
|
|
85
|
+ Genex offers a number of settings to adjust the algorithm to your liking. You can adjust: strategies, rates, and more. See the [configuration](https://hexdocs.pm/genex/introduction-configuration.html) guide for a full list.
|
|
83
86
|
|
|
84
|
- ## Strategies
|
|
85
|
- - `:crossover_type`- `:single_point`, `:two_point`, `:uniform`, `:blend`
|
|
86
|
- - `:mutation_type`- `:scramble`, `:invert`, `:bit_flip`
|
|
87
|
- - `:parent_selection`- `:natural`, `:random`, `:worst`
|
|
88
|
- - `:survivor_selection`- `:natural`, `:random`, `:worst`
|
|
87
|
+ ## Customization
|
|
89
88
|
|
|
90
|
- ## Rates
|
|
91
|
- - `:crossover_rate`- between 0 and 1
|
|
92
|
- - `:mutation_rate`- between 0 and 1
|
|
93
|
-
|
|
94
|
- ## Population
|
|
95
|
- - `:population_size`- `integer` greater than 0
|
|
96
|
-
|
|
97
|
- ## Unique to some Strategies
|
|
98
|
- - `:uniform_crossover_rate`- between 0 and 1 (Uniform Crossover)
|
|
99
|
- - `:alpha`- between 0 and 1 (Blend Crossover)
|
|
100
|
-
|
|
101
|
- # Customization
|
|
102
|
-
|
|
103
|
- You can customize every step of your genetic algorithm utilizing some of the many callbacks Genex provides. A list of callbacks is provided below.
|
|
104
|
-
|
|
105
|
- - `seed/0` - Seed the Population.
|
|
106
|
- - `evaluate/1` - Evaluate the entire Population.
|
|
107
|
- - `cycle/1` - The Genetic Algorithm Cycle.
|
|
108
|
- - `select_parents/1` - Select Parents for Crossover.
|
|
109
|
- - `crossover/1` - Perform Crossover.
|
|
110
|
- - `mutate/1` - Perform Mutation.
|
|
111
|
- - `select_survivors/1` - Select a number of chromosomes to survive.
|
|
112
|
- - `advance/1` - Advance to the next generation.
|
|
89
|
+ You can customize every step of your genetic algorithm utilizing one or more of the many callbacks Genex provides. See the [customization](https://hexdocs.pm/genex/introduction-customization.html) guide for more.
|
|
113
90
|
"""
|
|
114
91
|
|
|
115
92
|
@doc """
|
|
|
@@ -148,43 +125,40 @@ defmodule Genex do
|
|
148
125
|
@callback mutation_rate(Population.t()) :: number()
|
|
149
126
|
|
|
150
127
|
@doc """
|
|
151
|
- Radiation level is affects the "aggressiveness" of mutations.
|
|
128
|
+ Radiation level (aggressiveness) of mutation as a function of the population.
|
|
152
129
|
"""
|
|
153
130
|
@callback radiation(Population.t()) :: number()
|
|
154
131
|
|
|
155
132
|
@doc """
|
|
156
|
- Selects a number of individuals for crossover.
|
|
157
|
- The number of individuals selected depends on the crossover rate. This phase populates the `parent` field of the population struct with a `List` of tuples. Each tuple is a pair of parents to crossover.
|
|
133
|
+ Selects a number of individuals for crossover, depending on the `crossover_rate`.
|
|
158
134
|
"""
|
|
159
|
- @callback select_parents(population :: Population.t()) :: {:ok, Population.t()} | {:error, any()}
|
|
135
|
+ @callback select_parents(population :: Population.t()) ::
|
|
136
|
+ {:ok, Population.t()} | {:error, any()}
|
|
160
137
|
|
|
161
138
|
@doc """
|
|
162
139
|
Crossover a number of individuals to create a new population.
|
|
163
|
- The number of individuals depends on the crossover rate. This phase populates the `children` field of the populaton struct with a `List` of `Chromosomes`.
|
|
164
140
|
"""
|
|
165
141
|
@callback crossover(population :: Population.t()) :: {:ok, Population.t()} | {:error, any()}
|
|
166
142
|
|
|
167
143
|
@doc """
|
|
168
|
- Mutate a number of individuals to add novelty to the population.
|
|
169
|
- The number of individuals depends on the mutation rate. This phase populates the `mutant` field of the population struct with a `List` of `Chromosomes`.
|
|
144
|
+ Mutate a number of individuals, depending on the `mutation_rate`.
|
|
170
145
|
"""
|
|
171
146
|
@callback mutate(population :: Population.t()) :: {:ok, Population.t()} | {:error, any()}
|
|
172
147
|
|
|
173
148
|
@doc """
|
|
174
|
- Select a number of individuals to survive to the next generation.
|
|
175
|
- The number of individuals depends on the survival rate. This phase populates the `survivors` field of the population struct with a `List` of `Chromosomes`.
|
|
149
|
+ Select a number of individuals to survive to the next generation, depending on the `crossover_rate`.s
|
|
176
150
|
"""
|
|
177
|
- @callback select_survivors(population :: Population.t()) :: {:ok, Population.t()} | {:error, any()}
|
|
151
|
+ @callback select_survivors(population :: Population.t()) ::
|
|
152
|
+ {:ok, Population.t()} | {:error, any()}
|
|
178
153
|
|
|
179
154
|
@doc """
|
|
180
155
|
Tests the population for some termination criteria.
|
|
181
156
|
"""
|
|
182
|
- @callback terminate?(population :: Population.t) :: boolean()
|
|
157
|
+ @callback terminate?(population :: Population.t()) :: boolean()
|
|
183
158
|
|
|
184
159
|
defmacro __using__(opts \\ []) do
|
|
185
160
|
# Population
|
|
186
161
|
population_size = Keyword.get(opts, :population_size, 100)
|
|
187
|
- track_history? = Keyword.get(opts, :track_history?, false)
|
|
188
162
|
|
|
189
163
|
# Strategies
|
|
190
164
|
parent_selection_type = Keyword.get(opts, :parent_selection, :natural)
|
|
|
@@ -205,10 +179,10 @@ defmodule Genex do
|
|
205
179
|
|
|
206
180
|
alias Genex.Chromosome
|
|
207
181
|
alias Genex.Population
|
|
182
|
+ alias Genex.Support.Statistics
|
|
208
183
|
|
|
209
184
|
# Population Characteristics
|
|
210
185
|
@population_size unquote(population_size)
|
|
211
|
- @track_history? unquote(track_history?)
|
|
212
186
|
|
|
213
187
|
# Strategies
|
|
214
188
|
@crossover_type unquote(crossover_type)
|
|
|
@@ -273,13 +247,18 @@ defmodule Genex do
|
|
273
247
|
@spec seed :: {:ok, Chromosome.t()}
|
|
274
248
|
def seed do
|
|
275
249
|
history = Genealogy.init()
|
|
250
|
+
|
|
276
251
|
chromosomes =
|
|
277
252
|
for n <- 1..@population_size do
|
|
278
253
|
g = encoding()
|
|
279
254
|
c = %Chromosome{genes: g, size: length(g)}
|
|
280
|
- if @track_history?, do: Genealogy.update(history, c)
|
|
281
255
|
c
|
|
282
256
|
end
|
|
257
|
+
|
|
258
|
+ history =
|
|
259
|
+ history
|
|
260
|
+ |> Genealogy.add_generation(chromosomes)
|
|
261
|
+
|
|
283
262
|
pop = %Population{chromosomes: chromosomes, size: @population_size, history: history}
|
|
284
263
|
{:ok, pop}
|
|
285
264
|
end
|
|
|
@@ -299,8 +278,16 @@ defmodule Genex do
|
|
299
278
|
chromosomes =
|
|
300
279
|
population.chromosomes
|
|
301
280
|
|> Enum.map(fn c -> %Chromosome{c | fitness: fitness_function(c)} end)
|
|
281
|
+
|
|
302
282
|
strongest = Enum.max_by(chromosomes, &Chromosome.get_fitness/1)
|
|
303
|
- pop = %Population{population | chromosomes: chromosomes, strongest: strongest, max_fitness: strongest.fitness}
|
|
283
|
+
|
|
284
|
+ pop = %Population{
|
|
285
|
+ population
|
|
286
|
+ | chromosomes: chromosomes,
|
|
287
|
+ strongest: strongest,
|
|
288
|
+ max_fitness: strongest.fitness
|
|
289
|
+ }
|
|
290
|
+
|
|
304
291
|
{:ok, pop}
|
|
305
292
|
end
|
|
306
293
|
|
|
|
@@ -347,6 +334,7 @@ defmodule Genex do
|
|
347
334
|
{:ok, population}
|
|
348
335
|
else
|
|
349
336
|
Text.display_summary(population)
|
|
337
|
+
|
|
350
338
|
with {:ok, population} <- select_parents(population),
|
|
351
339
|
{:ok, population} <- crossover(population),
|
|
352
340
|
{:ok, population} <- mutate(population),
|
|
|
@@ -354,7 +342,7 @@ defmodule Genex do
|
|
354
342
|
{:ok, population} <- advance(population),
|
|
355
343
|
{:ok, population} <- evaluate(population),
|
|
356
344
|
{:ok, population} <- do_statistics(population) do
|
|
357
|
- cycle(population)
|
|
345
|
+ cycle(population)
|
|
358
346
|
else
|
|
359
347
|
{:error, reason} -> raise reason
|
|
360
348
|
end
|
|
|
@@ -374,13 +362,33 @@ defmodule Genex do
|
|
374
362
|
@spec select_parents(Population.t()) :: {:ok, Population.t()} | {:error, String.t()}
|
|
375
363
|
def select_parents(population) do
|
|
376
364
|
case @parent_selection_type do
|
|
377
|
- :natural -> do_parent_selection(population, crossover_rate(population), &Selection.natural/2, [])
|
|
378
|
- :worst -> do_parent_selection(population, crossover_rate(population), &Selection.worst/2, [])
|
|
379
|
- :random -> do_parent_selection(population, crossover_rate(population), &Selection.random/2, [])
|
|
380
|
- :roulette -> do_parent_selection(population, crossover_rate(population), &Selection.roulette/2, [])
|
|
381
|
- :tournament -> do_parent_selection(population, crossover_rate(population), &Selection.tournament/3, [@tournsize])
|
|
382
|
- :stochastic -> do_parent_selection(population, crossover_rate(population), &Selection.stochastic_universal_sampling/2, [])
|
|
383
|
- _ -> {:error, "Invalid Selection Type"}
|
|
365
|
+ :natural ->
|
|
366
|
+ do_parent_selection(population, crossover_rate(population), &Selection.natural/2, [])
|
|
367
|
+
|
|
368
|
+ :worst ->
|
|
369
|
+ do_parent_selection(population, crossover_rate(population), &Selection.worst/2, [])
|
|
370
|
+
|
|
371
|
+ :random ->
|
|
372
|
+ do_parent_selection(population, crossover_rate(population), &Selection.random/2, [])
|
|
373
|
+
|
|
374
|
+ :roulette ->
|
|
375
|
+ do_parent_selection(population, crossover_rate(population), &Selection.roulette/2, [])
|
|
376
|
+
|
|
377
|
+ :tournament ->
|
|
378
|
+ do_parent_selection(population, crossover_rate(population), &Selection.tournament/3, [
|
|
379
|
+ @tournsize
|
|
380
|
+ ])
|
|
381
|
+
|
|
382
|
+ :stochastic ->
|
|
383
|
+ do_parent_selection(
|
|
384
|
+ population,
|
|
385
|
+ crossover_rate(population),
|
|
386
|
+ &Selection.stochastic_universal_sampling/2,
|
|
387
|
+ []
|
|
388
|
+ )
|
|
389
|
+
|
|
390
|
+ _ ->
|
|
391
|
+ {:error, "Invalid Selection Type"}
|
|
384
392
|
end
|
|
385
393
|
end
|
|
386
394
|
|
|
|
@@ -397,14 +405,14 @@ defmodule Genex do
|
|
397
405
|
@spec crossover(Population.t()) :: {:ok, Population.t()} | {:error, String.t()}
|
|
398
406
|
def crossover(population) do
|
|
399
407
|
case @crossover_type do
|
|
400
|
- :single_point -> do_crossover(population, &Crossover.single_point/2, [])
|
|
401
|
- :two_point -> do_crossover(population, &Crossover.two_point/2, [])
|
|
402
|
- :uniform -> do_crossover(population, &Crossover.uniform/3, [@uniform_crossover_rate])
|
|
403
|
- :blend -> do_crossover(population, &Crossover.blend/3, [@alpha])
|
|
404
|
- :simulated_binary -> do_crossover(population, &Crossover.simulated_binary/3, [@eta])
|
|
408
|
+ :single_point -> do_crossover(population, &Crossover.single_point/2, [])
|
|
409
|
+ :two_point -> do_crossover(population, &Crossover.two_point/2, [])
|
|
410
|
+ :uniform -> do_crossover(population, &Crossover.uniform/3, [@uniform_crossover_rate])
|
|
411
|
+ :blend -> do_crossover(population, &Crossover.blend/3, [@alpha])
|
|
412
|
+ :simulated_binary -> do_crossover(population, &Crossover.simulated_binary/3, [@eta])
|
|
405
413
|
:messy_single_point -> do_crossover(population, &Crossover.messy_single_point/2, [])
|
|
406
|
- :davis_order -> do_crossover(population, &Crossover.davis_order/2, [])
|
|
407
|
- _ -> {:error, "Invalid Crossover Type."}
|
|
414
|
+ :davis_order -> do_crossover(population, &Crossover.davis_order/2, [])
|
|
415
|
+ _ -> {:error, "Invalid Crossover Type."}
|
|
408
416
|
end
|
|
409
417
|
end
|
|
410
418
|
|
|
|
@@ -421,14 +429,38 @@ defmodule Genex do
|
|
421
429
|
@spec mutate(Population.t()) :: {:ok, Population.t()} | {:error, String.t()}
|
|
422
430
|
def mutate(population) do
|
|
423
431
|
case @mutation_type do
|
|
424
|
- :bit_flip -> do_mutation(population, &Mutation.bit_flip/2, [radiation(population)])
|
|
425
|
- :scramble -> do_mutation(population, &Mutation.scramble/2, [radiation(population)])
|
|
426
|
- :invert -> do_mutation(population, &Mutation.invert/2, [radiation(population)])
|
|
427
|
- :uniform_integer -> do_mutation(population, &Mutation.uniform_integer/4, [radiation(population), @min, @max])
|
|
428
|
- :gaussian -> do_mutation(population, &Mutation.gaussian/2, [radiation(population)])
|
|
429
|
- :polynomial_bounded -> do_mutation(population, &Mutation.polynomial_bounded/5, [radiation(population), @eta, @min, @max])
|
|
430
|
- :none -> {:ok, population}
|
|
431
|
- _ -> {:error, "Invalid Mutation Type."}
|
|
432
|
+ :bit_flip ->
|
|
433
|
+ do_mutation(population, &Mutation.bit_flip/2, [radiation(population)])
|
|
434
|
+
|
|
435
|
+ :scramble ->
|
|
436
|
+ do_mutation(population, &Mutation.scramble/2, [radiation(population)])
|
|
437
|
+
|
|
438
|
+ :invert ->
|
|
439
|
+ do_mutation(population, &Mutation.invert/2, [radiation(population)])
|
|
440
|
+
|
|
441
|
+ :uniform_integer ->
|
|
442
|
+ do_mutation(population, &Mutation.uniform_integer/4, [
|
|
443
|
+ radiation(population),
|
|
444
|
+ @min,
|
|
445
|
+ @max
|
|
446
|
+ ])
|
|
447
|
+
|
|
448
|
+ :gaussian ->
|
|
449
|
+ do_mutation(population, &Mutation.gaussian/2, [radiation(population)])
|
|
450
|
+
|
|
451
|
+ :polynomial_bounded ->
|
|
452
|
+ do_mutation(population, &Mutation.polynomial_bounded/5, [
|
|
453
|
+ radiation(population),
|
|
454
|
+ @eta,
|
|
455
|
+ @min,
|
|
456
|
+ @max
|
|
457
|
+ ])
|
|
458
|
+
|
|
459
|
+ :none ->
|
|
460
|
+ {:ok, population}
|
|
461
|
+
|
|
462
|
+ _ ->
|
|
463
|
+ {:error, "Invalid Mutation Type."}
|
|
432
464
|
end
|
|
433
465
|
end
|
|
434
466
|
|
|
|
@@ -445,13 +477,26 @@ defmodule Genex do
|
|
445
477
|
@spec select_survivors(Population.t()) :: {:ok, Population.t()} | {:error, String.t()}
|
|
446
478
|
def select_survivors(population) do
|
|
447
479
|
case @survivor_selection_type do
|
|
448
|
- :natural -> do_survivor_selection(population, &Selection.natural/2, [])
|
|
449
|
- :worst -> do_survivor_selection(population, &Selection.worst/2, [])
|
|
450
|
- :random -> do_survivor_selection(population, &Selection.random/2, [])
|
|
451
|
- :roulette -> do_survivor_selection(population, &Selection.roulette/2, [])
|
|
452
|
- :tournament -> do_survivor_selection(population, &Selection.tournament/3, [@tournsize])
|
|
453
|
- :stochastic -> do_survivor_selection(population, &Selection.stochastic_universal_sampling/2, [])
|
|
454
|
- _ -> {:error, "Invalid Selection Type"}
|
|
480
|
+ :natural ->
|
|
481
|
+ do_survivor_selection(population, &Selection.natural/2, [])
|
|
482
|
+
|
|
483
|
+ :worst ->
|
|
484
|
+ do_survivor_selection(population, &Selection.worst/2, [])
|
|
485
|
+
|
|
486
|
+ :random ->
|
|
487
|
+ do_survivor_selection(population, &Selection.random/2, [])
|
|
488
|
+
|
|
489
|
+ :roulette ->
|
|
490
|
+ do_survivor_selection(population, &Selection.roulette/2, [])
|
|
491
|
+
|
|
492
|
+ :tournament ->
|
|
493
|
+ do_survivor_selection(population, &Selection.tournament/3, [@tournsize])
|
|
494
|
+
|
|
495
|
+ :stochastic ->
|
|
496
|
+ do_survivor_selection(population, &Selection.stochastic_universal_sampling/2, [])
|
|
497
|
+
|
|
498
|
+ _ ->
|
|
499
|
+ {:error, "Invalid Selection Type"}
|
|
455
500
|
end
|
|
456
501
|
end
|
|
457
502
|
|
|
|
@@ -467,13 +512,25 @@ defmodule Genex do
|
|
467
512
|
"""
|
|
468
513
|
@spec advance(Population.t()) :: {:ok, Population.t()}
|
|
469
514
|
def advance(population) do
|
|
470
|
- generation = population.generation+1
|
|
515
|
+ generation = population.generation + 1
|
|
516
|
+
|
|
471
517
|
survivors =
|
|
472
518
|
population.survivors
|
|
473
|
- |> Enum.map(fn c -> %Chromosome{c | age: c.age+1} end)
|
|
519
|
+ |> Enum.map(fn c -> %Chromosome{c | age: c.age + 1} end)
|
|
520
|
+
|
|
474
521
|
chromosomes = survivors ++ population.children
|
|
475
522
|
size = length(chromosomes)
|
|
476
|
- pop = %Population{population | size: size, chromosomes: chromosomes, generation: generation, children: nil, parents: nil, survivors: nil}
|
|
523
|
+
|
|
524
|
+ pop = %Population{
|
|
525
|
+ population
|
|
526
|
+ | size: size,
|
|
527
|
+ chromosomes: chromosomes,
|
|
528
|
+ generation: generation,
|
|
529
|
+ children: nil,
|
|
530
|
+ parents: nil,
|
|
531
|
+ survivors: nil
|
|
532
|
+ }
|
|
533
|
+
|
|
477
534
|
{:ok, pop}
|
|
478
535
|
end
|
|
479
536
|
|
|
|
@@ -487,11 +544,12 @@ defmodule Genex do
|
|
487
544
|
@spec run :: Population.t()
|
|
488
545
|
def run do
|
|
489
546
|
Text.init()
|
|
547
|
+
|
|
490
548
|
with {:ok, population} <- seed(),
|
|
491
549
|
{:ok, population} <- evaluate(population),
|
|
492
550
|
{:ok, population} <- cycle(population) do
|
|
493
|
- soln = Population.sort(population)
|
|
494
|
- soln
|
|
551
|
+ soln = Population.sort(population)
|
|
552
|
+ soln
|
|
495
553
|
else
|
|
496
554
|
{:error, reason} -> raise reason
|
|
497
555
|
end
|
|
|
@@ -515,6 +573,7 @@ defmodule Genex do
|
|
515
573
|
{:ok, survivor_pop} = select_survivors(mutated_pop)
|
|
516
574
|
genes = encoding()
|
|
517
575
|
c = %Chromosome{genes: genes, size: length(genes)}
|
|
576
|
+
|
|
518
577
|
Benchee.run(%{
|
|
519
578
|
"encoding/0" => fn -> encoding() end,
|
|
520
579
|
"seed/0" => fn -> seed() end,
|
|
|
@@ -526,57 +585,66 @@ defmodule Genex do
|
|
526
585
|
"mutate/1" => fn -> mutate(child_pop) end,
|
|
527
586
|
"select_survivors/1" => fn -> select_survivors(mutated_pop) end
|
|
528
587
|
})
|
|
588
|
+
|
|
529
589
|
:ok
|
|
530
590
|
end
|
|
531
591
|
|
|
532
592
|
defp do_crossover(population, f, args) do
|
|
533
593
|
parents = population.parents
|
|
534
|
- children =
|
|
594
|
+
|
|
595
|
+ {children, history} =
|
|
535
596
|
parents
|
|
536
|
- |> Enum.map(
|
|
537
|
- fn {p1, p2} ->
|
|
597
|
+ |> Enum.reduce(
|
|
598
|
+ {[], population.history},
|
|
599
|
+ fn {p1, p2}, {chd, his} ->
|
|
538
600
|
{c1, c2} = apply(f, [p1, p2] ++ args)
|
|
539
|
- if @track_history? do
|
|
540
|
- Genealogy.update(population.history, c1, p1, p2)
|
|
541
|
- Genealogy.update(population.history, c2, p1, p2)
|
|
542
|
- end
|
|
543
|
- [c1, c2]
|
|
601
|
+
|
|
602
|
+ newHis =
|
|
603
|
+ his
|
|
604
|
+ |> Genealogy.update(c1, p1, p2)
|
|
605
|
+ |> Genealogy.update(c1, p1, p2)
|
|
606
|
+
|
|
607
|
+ {[c1 | [c2 | chd]], newHis}
|
|
544
608
|
end
|
|
545
609
|
)
|
|
546
|
- |> List.flatten
|
|
547
|
- pop = %Population{population | children: children}
|
|
610
|
+
|
|
611
|
+ pop = %Population{population | children: children, history: history}
|
|
548
612
|
{:ok, pop}
|
|
549
613
|
end
|
|
550
614
|
|
|
551
615
|
defp do_mutation(population, f, args) do
|
|
552
616
|
u = mutation_rate(population)
|
|
617
|
+
|
|
553
618
|
chromosomes =
|
|
554
619
|
population.chromosomes
|
|
555
|
- |> Enum.map(
|
|
556
|
- fn c ->
|
|
557
|
- if :rand.uniform() < u do
|
|
558
|
- apply(f, [c] ++ args)
|
|
559
|
- else
|
|
560
|
- c
|
|
561
|
- end
|
|
620
|
+ |> Enum.map(fn c ->
|
|
621
|
+ if :rand.uniform() < u do
|
|
622
|
+ apply(f, [c] ++ args)
|
|
623
|
+ else
|
|
624
|
+ c
|
|
562
625
|
end
|
|
563
|
- )
|
|
564
|
- pop = %Population{population | chromosomes: chromosomes}
|
|
565
|
- {:ok, pop}
|
|
626
|
+ end)
|
|
627
|
+
|
|
628
|
+ pop = %Population{population | chromosomes: chromosomes}
|
|
629
|
+ {:ok, pop}
|
|
566
630
|
end
|
|
567
631
|
|
|
568
|
- defp do_parent_selection(population, rate, f, args) when is_float(rate) and rate >= 0.0 and rate <= 1.0 do
|
|
632
|
+ defp do_parent_selection(population, rate, f, args)
|
|
633
|
+ when is_float(rate) and rate >= 0.0 and rate <= 1.0 do
|
|
569
634
|
chromosomes = population.chromosomes
|
|
570
635
|
n = floor(rate * length(chromosomes))
|
|
636
|
+
|
|
571
637
|
parents =
|
|
572
638
|
f
|
|
573
639
|
|> apply([chromosomes, n] ++ args)
|
|
574
640
|
|> Enum.chunk_every(2, 2, :discard)
|
|
575
641
|
|> Enum.map(fn f -> List.to_tuple(f) end)
|
|
642
|
+
|
|
576
643
|
pop = %Population{population | parents: parents}
|
|
577
644
|
{:ok, pop}
|
|
578
645
|
end
|
|
579
|
- defp do_parent_selection(_, _, _, _), do: raise "Invalid crossover rate!"
|
|
646
|
+
|
|
647
|
+ defp do_parent_selection(_, _, _, _), do: raise("Invalid crossover rate!")
|
|
580
648
|
|
|
581
649
|
defp do_survivor_selection(population, f, args) do
|
|
582
650
|
chromosomes = population.chromosomes
|
|
|
@@ -589,33 +657,31 @@ defmodule Genex do
|
|
589
657
|
defp do_statistics(population) do
|
|
590
658
|
stats =
|
|
591
659
|
statistics()
|
|
592
|
- |> Enum.map(
|
|
593
|
- fn {k, v} ->
|
|
594
|
- val =
|
|
595
|
- population.chromosomes
|
|
596
|
- |> Enum.map(fn c -> c.fitness end)
|
|
597
|
- |> v.()
|
|
598
|
- {:"#{k}", val}
|
|
599
|
- end
|
|
600
|
- )
|
|
660
|
+ |> Enum.map(fn {k, v} ->
|
|
661
|
+ val =
|
|
662
|
+ population.chromosomes
|
|
663
|
+ |> Enum.map(fn c -> c.fitness end)
|
|
664
|
+ |> v.()
|
|
665
|
+
|
|
666
|
+ {:"#{k}", val}
|
|
667
|
+ end)
|
|
668
|
+
|
|
601
669
|
pop = %Population{population | statistics: stats}
|
|
602
670
|
{:ok, pop}
|
|
603
671
|
end
|
|
604
672
|
|
|
605
|
- defoverridable [
|
|
606
|
- select_parents: 1,
|
|
607
|
- crossover: 1,
|
|
608
|
- mutate: 1,
|
|
609
|
- select_survivors: 1,
|
|
610
|
- seed: 0,
|
|
611
|
- evaluate: 1,
|
|
612
|
- advance: 1,
|
|
613
|
- cycle: 1,
|
|
614
|
- statistics: 0
|
|
615
|
- ]
|
|
673
|
+ defoverridable select_parents: 1,
|
|
674
|
+ crossover: 1,
|
|
675
|
+ mutate: 1,
|
|
676
|
+ select_survivors: 1,
|
|
677
|
+ seed: 0,
|
|
678
|
+ evaluate: 1,
|
|
679
|
+ advance: 1,
|
|
680
|
+ cycle: 1,
|
|
681
|
+ statistics: 0,
|
|
682
|
+ benchmark: 0
|
|
616
683
|
end
|
|
617
684
|
end
|
|
618
685
|
|
|
619
686
|
defguard valid_rate?(rate) when is_float(rate) and rate >= 0.0 and rate <= 1.0
|
|
620
|
-
|
|
621
687
|
end
|
changed
lib/genex/chromosome.ex
|
|
@@ -1,5 +1,6 @@
|
|
1
1
|
defmodule Genex.Chromosome do
|
|
2
2
|
alias __MODULE__, as: Chromosome
|
|
3
|
+
|
|
3
4
|
@moduledoc """
|
|
4
5
|
A collection of genes.
|
|
5
6
|
|
|
|
@@ -7,11 +8,11 @@ defmodule Genex.Chromosome do
|
|
7
8
|
"""
|
|
8
9
|
|
|
9
10
|
@type t :: %Chromosome{
|
|
10
|
- genes: Enum.t,
|
|
11
|
- fitness: number(),
|
|
12
|
- size: integer(),
|
|
13
|
- age: integer()
|
|
14
|
- }
|
|
11
|
+ genes: Enum.t(),
|
|
12
|
+ fitness: number(),
|
|
13
|
+ size: integer(),
|
|
14
|
+ age: integer()
|
|
15
|
+ }
|
|
15
16
|
|
|
16
17
|
@enforce_keys [:genes]
|
|
17
18
|
defstruct [:genes, fitness: 0, size: 0, age: 0]
|
changed
lib/genex/operators/crossover.ex
|
|
@@ -1,5 +1,6 @@
|
|
1
1
|
defmodule Genex.Operators.Crossover do
|
|
2
2
|
alias Genex.Chromosome
|
|
3
|
+
|
|
3
4
|
@moduledoc """
|
|
4
5
|
Implementation of several popular crossover methods.
|
|
5
6
|
|
|
|
@@ -13,55 +14,150 @@ defmodule Genex.Operators.Crossover do
|
|
13
14
|
"""
|
|
14
15
|
|
|
15
16
|
@doc """
|
|
16
|
- Performs single point crossover.
|
|
17
|
+ Performs single point crossover at a random point.
|
|
17
18
|
|
|
18
|
- This will swap a slice of genes from each chromosome, producing 2 new chromosomes.
|
|
19
|
+ This will swap a random slice of genes from each chromosome, producing 2 new chromosomes.
|
|
19
20
|
|
|
20
|
- Returns `%Chromosome{}`.
|
|
21
|
+ Returns `{%Chromosome{}, %Chromosome{}}`.
|
|
21
22
|
|
|
22
23
|
# Parameters
|
|
23
|
- - `p1`: Parent One.
|
|
24
|
- - `p2`: Parent Two.
|
|
24
|
+ - `p1`: Parent one.
|
|
25
|
+ - `p2`: Parent two.
|
|
25
26
|
"""
|
|
26
27
|
@spec single_point(Chromosome.t(), Chromosome.t()) :: {Chromosome.t(), Chromosome.t()}
|
|
27
28
|
def single_point(p1, p2) do
|
|
28
29
|
chromosome_length = p1.size
|
|
29
|
- point = floor(chromosome_length * :rand.uniform())
|
|
30
|
- {g1, g2} = Enum.split(p1.genes, point)
|
|
31
|
- {g3, g4} = Enum.split(p2.genes, point)
|
|
32
|
- {c1, c2} = {g1 ++ g4, g3 ++ g2}
|
|
33
|
- {%Chromosome{genes: c1, size: p1.size}, %Chromosome{genes: c2, size: p1.size}}
|
|
30
|
+ point = :rand.uniform(chromosome_length)
|
|
31
|
+ single_point(p1, p2, point)
|
|
34
32
|
end
|
|
35
33
|
|
|
36
34
|
@doc """
|
|
37
|
- Performs two-point crossover.
|
|
35
|
+ Performs single point crossover at a known point.
|
|
38
36
|
|
|
39
|
- This will swap multiple slices of genes from each chromosome, producing 2 new chromosomes.
|
|
37
|
+ This will swap a known slice of genes from each chromosome, producing 2 new chromosomes.
|
|
38
|
+
|
|
39
|
+ Returns `{%Chromosome{}, %Chromosome{}}`.
|
|
40
|
+
|
|
41
|
+ # Parameters
|
|
42
|
+ - `p1`: Parent one.
|
|
43
|
+ - `p2`: Parent two.
|
|
44
|
+ - `point`: Slice to swap.
|
|
45
|
+
|
|
46
|
+ # Examples
|
|
47
|
+
|
|
48
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
49
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
50
|
+ iex> single_point(c1, c2, 2)
|
|
51
|
+ {%#{Chromosome}{genes: [1, 2, 8, 9, 10], size: 5}, %#{Chromosome}{genes: [6, 7, 3, 4, 5], size: 5}}
|
|
52
|
+
|
|
53
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
54
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
55
|
+ iex> single_point(c1, c2, 10)
|
|
56
|
+ {%#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}, %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}}
|
|
57
|
+
|
|
58
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
59
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
60
|
+ iex> single_point(c1, c2, 0)
|
|
61
|
+ {%#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}, %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}}
|
|
62
|
+
|
|
63
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
64
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
65
|
+ iex> single_point(c1, c2, -5)
|
|
66
|
+ {%#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}, %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}}
|
|
67
|
+ """
|
|
68
|
+ @spec single_point(Chromosome.t(), Chromosome.t()) :: {Chromosome.t(), Chromosome.t()}
|
|
69
|
+ def single_point(p1, p2, point) when point <= 0,
|
|
70
|
+ do: {%Chromosome{genes: p1.genes, size: p1.size}, %Chromosome{genes: p2.genes, size: p2.size}}
|
|
71
|
+
|
|
72
|
+ def single_point(p1, p2, point) do
|
|
73
|
+ {g1, g2} = Enum.split(p1.genes, point)
|
|
74
|
+ {g3, g4} = Enum.split(p2.genes, point)
|
|
75
|
+ {c1, c2} = {g1 ++ g4, g3 ++ g2}
|
|
76
|
+ {%Chromosome{genes: c1, size: length(c1)}, %Chromosome{genes: c2, size: length(c2)}}
|
|
77
|
+ end
|
|
78
|
+
|
|
79
|
+ @doc """
|
|
80
|
+ Performs two-point crossover at a random point.
|
|
81
|
+
|
|
82
|
+ This will swap two random slices of genes from each chromosome, producing 2 new chromosomes.
|
|
40
83
|
|
|
41
84
|
Returns `%Chromosome{}`.
|
|
42
85
|
|
|
43
86
|
# Parameters
|
|
44
|
- - `p1`: Parent One.
|
|
45
|
- - `p2`: Parent Two.
|
|
87
|
+ - `p1`: Parent one.
|
|
88
|
+ - `p2`: Parent two.
|
|
46
89
|
"""
|
|
47
|
- @spec two_point(Chromosome.t(), Chromosome.t()) :: Chromosome.t()
|
|
90
|
+ @spec two_point(Chromosome.t(), Chromosome.t()) :: {Chromosome.t(), Chromosome.t()}
|
|
48
91
|
def two_point(p1, p2) do
|
|
49
92
|
chromosome_length = p1.size
|
|
50
|
- a = :rand.uniform(chromosome_length-1)
|
|
51
|
- b = :rand.uniform(chromosome_length-2)
|
|
52
|
- point1 = if b >= a do a else b end
|
|
53
|
- point2 = if b >= a do b+1 else a end
|
|
93
|
+ a = :rand.uniform(chromosome_length - 1)
|
|
94
|
+ b = :rand.uniform(chromosome_length - 2)
|
|
95
|
+
|
|
96
|
+ point1 =
|
|
97
|
+ if b >= a do
|
|
98
|
+ a
|
|
99
|
+ else
|
|
100
|
+ b
|
|
101
|
+ end
|
|
102
|
+
|
|
103
|
+ point2 =
|
|
104
|
+ if b >= a do
|
|
105
|
+ b + 1
|
|
106
|
+ else
|
|
107
|
+ a
|
|
108
|
+ end
|
|
109
|
+
|
|
54
110
|
# Split
|
|
55
|
- {slice1, rem1} = Enum.split(p1.genes, point1)
|
|
56
|
- {slice2, rem2} = Enum.split(p2.genes, point1)
|
|
57
|
- {slice3, rem3} = Enum.split(rem1, point2-point1)
|
|
58
|
- {slice4, rem4} = Enum.split(rem2, point2-point1)
|
|
59
|
- {c1, c2} =
|
|
60
|
- {
|
|
61
|
- slice1 ++ slice4 ++ rem3,
|
|
62
|
- slice2 ++ slice3 ++ rem4
|
|
63
|
- }
|
|
64
|
- {%Chromosome{genes: c1, size: p1.size}, %Chromosome{genes: c2, size: p1.size}}
|
|
111
|
+ two_point(p1, p2, point1, point2)
|
|
112
|
+ end
|
|
113
|
+
|
|
114
|
+ @doc """
|
|
115
|
+ Performs two-point crossover at a known point.
|
|
116
|
+
|
|
117
|
+ This will swap a known slice of genes from each chromosome, producing 2 new chromosomes.
|
|
118
|
+
|
|
119
|
+ Returns `{%Chromosome{}, %Chromosome{}}`.
|
|
120
|
+
|
|
121
|
+ # Parameters
|
|
122
|
+ - `p1`: Parent one.
|
|
123
|
+ - `p2`: Parent two.
|
|
124
|
+ - `first`: First Split Point.
|
|
125
|
+ - `second`: Second Split Point.
|
|
126
|
+
|
|
127
|
+ # Examples
|
|
128
|
+
|
|
129
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
130
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
131
|
+ iex> two_point(c1, c2, 1, 3)
|
|
132
|
+ {%#{Chromosome}{genes: [1, 7, 8, 4, 5], size: 5}, %#{Chromosome}{genes: [6, 2, 3, 9, 10], size: 5}}
|
|
133
|
+
|
|
134
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
135
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
136
|
+ iex> two_point(c1, c2, 10, 3)
|
|
137
|
+ {%#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}, %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}}
|
|
138
|
+
|
|
139
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
140
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
141
|
+ iex> two_point(c1, c2, -3, 3)
|
|
142
|
+ {%#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}, %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}}
|
|
143
|
+ """
|
|
144
|
+ @spec two_point(Chromosome.t(), Chromosome.t(), integer(), integer()) ::
|
|
145
|
+ {Chromosome.t(), Chromosome.t()}
|
|
146
|
+ def two_point(p1, p2, first, second) when first < 0 or second < 0,
|
|
147
|
+ do: {%Chromosome{genes: p1.genes, size: p1.size}, %Chromosome{genes: p2.genes, size: p2.size}}
|
|
148
|
+
|
|
149
|
+ def two_point(p1, p2, first, second) do
|
|
150
|
+ {slice1, rem1} = Enum.split(p1.genes, first)
|
|
151
|
+ {slice2, rem2} = Enum.split(p2.genes, first)
|
|
152
|
+ {slice3, rem3} = Enum.split(rem1, second - first)
|
|
153
|
+ {slice4, rem4} = Enum.split(rem2, second - first)
|
|
154
|
+
|
|
155
|
+ {c1, c2} = {
|
|
156
|
+ slice1 ++ slice4 ++ rem3,
|
|
157
|
+ slice2 ++ slice3 ++ rem4
|
|
158
|
+ }
|
|
159
|
+
|
|
160
|
+ {%Chromosome{genes: c1, size: length(c1)}, %Chromosome{genes: c2, size: length(c2)}}
|
|
65
161
|
end
|
|
66
162
|
|
|
67
163
|
@doc """
|
|
|
@@ -72,8 +168,8 @@ defmodule Genex.Operators.Crossover do
|
|
72
168
|
Returns `Chromosome`.
|
|
73
169
|
|
|
74
170
|
# Parameters
|
|
75
|
- - `p1`: Parent One.
|
|
76
|
- - `p2`: Parent Two.
|
|
171
|
+ - `p1`: Parent one.
|
|
172
|
+ - `p2`: Parent two.
|
|
77
173
|
- `rate`: `Float` between 0 and 1 representing rates to swap genes.
|
|
78
174
|
"""
|
|
79
175
|
@spec uniform(Chromosome.t(), Chromosome.t(), float()) :: {Chromosome.t(), Chromosome.t()}
|
|
|
@@ -81,109 +177,161 @@ defmodule Genex.Operators.Crossover do
|
|
81
177
|
{c1, c2} =
|
|
82
178
|
p1.genes
|
|
83
179
|
|> Enum.zip(p2.genes)
|
|
84
|
- |> Enum.map(fn {x, y} -> if :rand.uniform < rate do {x, y} else {y, x} end end)
|
|
85
|
- |> Enum.unzip
|
|
180
|
+ |> Enum.map(fn {x, y} ->
|
|
181
|
+ if :rand.uniform() < rate do
|
|
182
|
+ {x, y}
|
|
183
|
+ else
|
|
184
|
+ {y, x}
|
|
185
|
+ end
|
|
186
|
+ end)
|
|
187
|
+ |> Enum.unzip()
|
|
188
|
+
|
|
86
189
|
{%Chromosome{genes: c1, size: p1.size}, %Chromosome{genes: c2, size: p1.size}}
|
|
87
190
|
end
|
|
88
191
|
|
|
89
192
|
@doc """
|
|
90
193
|
Performs a blend crossover.
|
|
91
194
|
|
|
92
|
- This will blend genes according to some alpha between 0 and 1. If alpha=.5, the resulting chromosomes will be identical to one another.
|
|
195
|
+ This will blend genes according to some alpha between 0 and 1.
|
|
93
196
|
|
|
94
|
- Returns `Chromosome`.
|
|
197
|
+ Returns `{%Chromosome{}, %Chromosome{}}`.
|
|
95
198
|
|
|
96
199
|
# Parameters
|
|
97
200
|
- `p1`: Parent one.
|
|
98
201
|
- `p2`: Parent two.
|
|
99
202
|
- `alpha`: `Float` between 0 and 1 representing percentage of each parent to blend into children.
|
|
100
203
|
"""
|
|
101
|
- @spec blend(Chromosome.t(), Chromosome.t(), float()) :: Chromosome.t()
|
|
204
|
+ @spec blend(Chromosome.t(), Chromosome.t(), float()) :: {Chromosome.t(), Chromosome.t()}
|
|
102
205
|
def blend(p1, p2, alpha) do
|
|
103
206
|
{c1, c2} =
|
|
104
207
|
p1.genes
|
|
105
208
|
|> Enum.zip(p2.genes)
|
|
106
|
- |> Enum.map(
|
|
107
|
- fn {x, y} ->
|
|
108
|
- gamma = (1 + 2 * alpha) * :rand.uniform() - alpha
|
|
109
|
- {
|
|
110
|
- (1 - gamma) * x + gamma * y,
|
|
111
|
- gamma * x + (1 - gamma) * y
|
|
112
|
- }
|
|
113
|
- end
|
|
114
|
- )
|
|
115
|
- |> Enum.unzip
|
|
209
|
+ |> Enum.map(fn {x, y} ->
|
|
210
|
+ gamma = (1 + 2 * alpha) * :rand.uniform() - alpha
|
|
211
|
+
|
|
212
|
+ {
|
|
213
|
+ (1 - gamma) * x + gamma * y,
|
|
214
|
+ gamma * x + (1 - gamma) * y
|
|
215
|
+ }
|
|
216
|
+ end)
|
|
217
|
+ |> Enum.unzip()
|
|
218
|
+
|
|
116
219
|
{%Chromosome{genes: c1, size: p1.size}, %Chromosome{genes: c2, size: p1.size}}
|
|
117
220
|
end
|
|
118
221
|
|
|
119
222
|
@doc """
|
|
120
223
|
Performs a simulated binary crossover.
|
|
121
224
|
|
|
122
|
- Returns `Chromosome`.
|
|
225
|
+ Returns `{%Chromosome{}, %Chromosome{}}`.
|
|
123
226
|
|
|
124
227
|
# Parameters
|
|
125
228
|
- `p1`: Parent one.
|
|
126
229
|
- `p2`: Parent two.
|
|
127
230
|
- `eta`: `Float`
|
|
128
231
|
"""
|
|
129
|
- @spec simulated_binary(Chromosome.t(), Chromosome.t(), number()) :: Chromosome.t()
|
|
232
|
+ @spec simulated_binary(Chromosome.t(), Chromosome.t(), number()) ::
|
|
233
|
+ {Chromosome.t(), Chromosome.t()}
|
|
130
234
|
def simulated_binary(p1, p2, eta) do
|
|
131
235
|
{c1, c2} =
|
|
132
236
|
p1.genes
|
|
133
237
|
|> Enum.zip(p2.genes)
|
|
134
|
- |> Enum.map(
|
|
135
|
- fn {x, y} ->
|
|
136
|
- rand = :rand.uniform()
|
|
137
|
- beta = if rand <= 0.5 do 2 * rand else 1/(2*(1-rand)) end
|
|
138
|
- beta = :math.pow(beta, (1/eta+1))
|
|
139
|
- {
|
|
140
|
- 0.5 * (((1 + beta) * x) + ((1 - beta) * y)),
|
|
141
|
- 0.5 * (((1 - beta) * x) + ((1 + beta) * y))
|
|
142
|
- }
|
|
238
|
+ |> Enum.map(fn {x, y} ->
|
|
239
|
+ rand = :rand.uniform()
|
|
240
|
+
|
|
241
|
+ beta =
|
|
242
|
+ if rand <= 0.5 do
|
|
243
|
+ 2 * rand
|
|
244
|
+ else
|
|
245
|
+ 1 / (2 * (1 - rand))
|
|
143
246
|
end
|
|
144
|
- )
|
|
145
|
- |> Enum.unzip
|
|
247
|
+
|
|
248
|
+ beta = :math.pow(beta, 1 / eta + 1)
|
|
249
|
+
|
|
250
|
+ {
|
|
251
|
+ 0.5 * ((1 + beta) * x + (1 - beta) * y),
|
|
252
|
+ 0.5 * ((1 - beta) * x + (1 + beta) * y)
|
|
253
|
+ }
|
|
254
|
+ end)
|
|
255
|
+ |> Enum.unzip()
|
|
256
|
+
|
|
146
257
|
{%Chromosome{genes: c1, size: p1.size}, %Chromosome{genes: c2, size: p1.size}}
|
|
147
258
|
end
|
|
148
259
|
|
|
149
260
|
@doc """
|
|
150
|
- Performs a messy single point crossover.
|
|
261
|
+ Performs a messy single point crossover at random points.
|
|
151
262
|
|
|
152
263
|
This crossover disregards the length of the chromosome and will often arbitrarily increase or decrease it's size.
|
|
153
264
|
|
|
154
|
- Returns `Chromosome`.
|
|
265
|
+ Returns `{%Chromosome{}, %Chromosome{}}`.
|
|
155
266
|
|
|
156
267
|
# Parameters
|
|
157
268
|
- `p1`: Parent one.
|
|
158
269
|
- `p2`: Parent two.
|
|
159
270
|
"""
|
|
160
|
- @spec messy_single_point(Chromosome.t(), Chromosome.t()) :: Chromosome.t()
|
|
271
|
+ @spec messy_single_point(Chromosome.t(), Chromosome.t()) :: {Chromosome.t(), Chromosome.t()}
|
|
161
272
|
def messy_single_point(p1, p2) do
|
|
162
273
|
chromosome_length = length(p1.genes)
|
|
163
|
- point = if chromosome_length == 0 do 0 else :rand.uniform(chromosome_length) end
|
|
164
|
- {c1, c2} = {
|
|
165
|
- Enum.slice(p1.genes, 0..point)
|
|
166
|
- ++ Enum.slice(p2.genes, 0..point),
|
|
167
|
- Enum.slice(p1.genes, point..chromosome_length-1)
|
|
168
|
- ++ Enum.slice(p1.genes, point..chromosome_length-1)
|
|
169
|
- }
|
|
274
|
+ point1 = if chromosome_length == 0, do: 0, else: :rand.uniform(chromosome_length)
|
|
275
|
+ point2 = if chromosome_length == 0, do: 0, else: :rand.uniform(chromosome_length)
|
|
276
|
+ messy_single_point(p1, p2, point1, point2)
|
|
277
|
+ end
|
|
278
|
+
|
|
279
|
+ @doc """
|
|
280
|
+ Performs a messy single point crossover at known points.
|
|
281
|
+
|
|
282
|
+ This crossover disregards the length of the chromosome and will often arbitrarily increase or decrease it's size.
|
|
283
|
+
|
|
284
|
+ Returns `{%Chromosome{}, %Chromosome{}}`.
|
|
285
|
+
|
|
286
|
+ # Parameters
|
|
287
|
+ - `p1`: Parent one.
|
|
288
|
+ - `p2`: Parent two.
|
|
289
|
+ - `point1`: `p1` split point.
|
|
290
|
+ - `point2`: `p2` split point.
|
|
291
|
+
|
|
292
|
+ # Examples
|
|
293
|
+
|
|
294
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
295
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
296
|
+ iex> messy_single_point(c1, c2, 2, 4)
|
|
297
|
+ {%#{Chromosome}{genes: [1, 2, 10], size: 3}, %#{Chromosome}{genes: [6, 7, 8, 9, 3, 4, 5], size: 7}}
|
|
298
|
+
|
|
299
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
300
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
301
|
+ iex> messy_single_point(c1, c2, 0, 10)
|
|
302
|
+ {%#{Chromosome}{genes: [], size: 0}, %#{Chromosome}{genes: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5], size: 10}}
|
|
303
|
+
|
|
304
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
305
|
+ iex> c2 = %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}
|
|
306
|
+ iex> messy_single_point(c1, c2, -2, 3)
|
|
307
|
+ {%#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}, %#{Chromosome}{genes: [6, 7, 8, 9, 10], size: 5}}
|
|
308
|
+ """
|
|
309
|
+ @spec messy_single_point(Chromosome.t(), Chromosome.t(), integer(), integer()) ::
|
|
310
|
+ {Chromosome.t(), Chromosome.t()}
|
|
311
|
+ def messy_single_point(p1, p2, point1, point2) when point1 < 0 or point2 < 0,
|
|
312
|
+ do: {%Chromosome{genes: p1.genes, size: 5}, %Chromosome{genes: p2.genes, size: 5}}
|
|
313
|
+
|
|
314
|
+ def messy_single_point(p1, p2, point1, point2) do
|
|
315
|
+ {g1, g2} = Enum.split(p1.genes, point1)
|
|
316
|
+ {g3, g4} = Enum.split(p2.genes, point2)
|
|
317
|
+ {c1, c2} = {g1 ++ g4, g3 ++ g2}
|
|
170
318
|
{%Chromosome{genes: c1, size: length(c1)}, %Chromosome{genes: c2, size: length(c2)}}
|
|
171
319
|
end
|
|
172
320
|
|
|
173
321
|
@doc """
|
|
174
|
- Performs Davis Order crossover.
|
|
322
|
+ Performs Davis Order crossover of a random slice.
|
|
175
323
|
|
|
176
|
- Returns `Chromosome`.
|
|
324
|
+ Returns `{%Chromosome{}, %Chromosome{}}`.
|
|
177
325
|
|
|
178
326
|
# Parameters
|
|
179
327
|
- `p1`: Parent one.
|
|
180
328
|
- `p2`: Parent two.
|
|
181
329
|
"""
|
|
182
|
- @spec davis_order(Chromosome.t(), Chromosome.t()) :: Chromosome.t()
|
|
330
|
+ @spec davis_order(Chromosome.t(), Chromosome.t()) :: {Chromosome.t(), Chromosome.t()}
|
|
183
331
|
def davis_order(p1, p2) do
|
|
184
|
- {a, b} = {:rand.uniform(p1.size-1), :rand.uniform(p1.size-2)}
|
|
332
|
+ {a, b} = {:rand.uniform(p1.size - 1), :rand.uniform(p1.size - 2)}
|
|
185
333
|
point1 = if b >= a, do: a, else: b
|
|
186
|
- point2 = if b >= a, do: b+1, else: a
|
|
334
|
+ point2 = if b >= a, do: b + 1, else: a
|
|
187
335
|
slice1 = Enum.slice(p1.genes, point1, point2)
|
|
188
336
|
slice2 = Enum.slice(p2.genes, point1, point2)
|
|
189
337
|
rem1 = Enum.filter(p1.genes, fn x -> x not in slice1 end)
|
changed
lib/genex/operators/mutation.ex
|
|
@@ -2,6 +2,7 @@ defmodule Genex.Operators.Mutation do
|
|
2
2
|
use Bitwise
|
|
3
3
|
alias Genex.Chromosome
|
|
4
4
|
import Genex, only: [valid_rate?: 1]
|
|
5
|
+
|
|
5
6
|
@moduledoc """
|
|
6
7
|
Implementation of several population mutation methods.
|
|
7
8
|
|
|
|
@@ -24,54 +25,70 @@ defmodule Genex.Operators.Mutation do
|
|
24
25
|
def bit_flip(chromosome, radiation) when valid_rate?(radiation) do
|
|
25
26
|
genes =
|
|
26
27
|
chromosome.genes
|
|
27
|
- |> Enum.map(
|
|
28
|
- fn x ->
|
|
29
|
- if :rand.uniform > radiation do
|
|
30
|
- 1 ^^^ x
|
|
31
|
- else
|
|
32
|
- x
|
|
33
|
- end
|
|
28
|
+ |> Enum.map(fn x ->
|
|
29
|
+ if :rand.uniform() > radiation do
|
|
30
|
+ 1 ^^^ x
|
|
31
|
+ else
|
|
32
|
+ x
|
|
34
33
|
end
|
|
35
|
- )
|
|
34
|
+ end)
|
|
35
|
+
|
|
36
36
|
%Chromosome{chromosome | genes: genes}
|
|
37
37
|
end
|
|
38
|
- def bit_flip(_, _), do: raise "Invalid radiation level!"
|
|
38
|
+
|
|
39
|
+ def bit_flip(_, _), do: raise(ArgumentError, message: "Invalid radiation level!")
|
|
39
40
|
|
|
40
41
|
@doc """
|
|
41
42
|
Perform a scramble mutation.
|
|
42
43
|
|
|
43
|
- This mutation shuffles the genes of the Chromosome.
|
|
44
|
+ This mutation shuffles the genes of the Chromosome between 2 random points.
|
|
44
45
|
|
|
45
|
- Returns `Chromosome`.
|
|
46
|
+ Returns `%Chromosome{}`.
|
|
46
47
|
|
|
47
48
|
# Parameters
|
|
48
|
- - `chromosome`- `Chromosome` to mutate.
|
|
49
|
+ - `chromosome`: `Chromosome` to mutate.
|
|
50
|
+ - `radiation`: Aggressiveness of the mutation.
|
|
49
51
|
"""
|
|
50
52
|
@spec scramble(Chromosome.t(), float()) :: Chromosome.t()
|
|
51
53
|
def scramble(chromosome, radiation) when valid_rate?(radiation) do
|
|
52
|
- p = floor(chromosome.size * radiation)
|
|
53
|
- genes =
|
|
54
|
- if p == chromosome.size-1 do
|
|
55
|
- chromosome.genes
|
|
56
|
- |> Enum.shuffle()
|
|
57
|
- else
|
|
58
|
- {head, tail} =
|
|
59
|
- chromosome.genes
|
|
60
|
- |> Enum.split(p)
|
|
61
|
- head
|
|
62
|
- |> Enum.shuffle()
|
|
63
|
- |> Kernel.++(tail)
|
|
64
|
- end
|
|
65
|
- %Chromosome{chromosome | genes: genes}
|
|
54
|
+ chromosome_length = chromosome.size
|
|
55
|
+ num_to_scramble = floor(radiation * chromosome_length)
|
|
56
|
+ point = if chromosome_length == 0, do: 0, else: :rand.uniform(chromosome_length)
|
|
57
|
+ scramble(chromosome, point, point + num_to_scramble)
|
|
66
58
|
end
|
|
67
|
- def scramble(_, _), do: raise "Invalid radiation level!"
|
|
59
|
+
|
|
60
|
+ def scramble(_, _), do: raise(ArgumentError, message: "Invalid radiation level!")
|
|
68
61
|
|
|
69
62
|
@doc """
|
|
70
|
- Perform inversion mutation.
|
|
63
|
+ Performs a scramble mutation of a known slice.
|
|
71
64
|
|
|
72
|
- This mutation reverses (inverts) the genes of the Chromosome.
|
|
65
|
+ This mutation shuffles the genes of a Chromosome between 2 known points.
|
|
73
66
|
|
|
74
|
- Returns `Chromosome`.
|
|
67
|
+ # Parameters
|
|
68
|
+ - `chromosome`: `Chromosome` to mutate.
|
|
69
|
+ - `start`: First scramble point.
|
|
70
|
+ - `finish`: Second scramble point.
|
|
71
|
+
|
|
72
|
+ # Examples
|
|
73
|
+
|
|
74
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
75
|
+ iex> scramble(c1, 10, 4)
|
|
76
|
+ %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
77
|
+ """
|
|
78
|
+ @spec scramble(Chromosome.t(), integer(), integer()) :: Chromosome.t()
|
|
79
|
+ def scramble(chromosome, start, finish) do
|
|
80
|
+ {head, slice} = Enum.split(chromosome.genes, start)
|
|
81
|
+ {slice, tail} = Enum.split(slice, finish - start)
|
|
82
|
+ genes = head ++ Enum.shuffle(slice) ++ tail
|
|
83
|
+ %Chromosome{chromosome | genes: genes}
|
|
84
|
+ end
|
|
85
|
+
|
|
86
|
+ @doc """
|
|
87
|
+ Perform inversion mutation on a random slice.
|
|
88
|
+
|
|
89
|
+ This mutation reverses (inverts) a random slice of genes of the Chromosome.
|
|
90
|
+
|
|
91
|
+ Returns `%Chromosome{}`.
|
|
75
92
|
|
|
76
93
|
# Parameters
|
|
77
94
|
- `chromosome`- `Chromosome` to mutate.
|
|
|
@@ -79,22 +96,47 @@ defmodule Genex.Operators.Mutation do
|
|
79
96
|
"""
|
|
80
97
|
@spec invert(Chromosome.t(), float()) :: Chromosome.t()
|
|
81
98
|
def invert(chromosome, radiation) when valid_rate?(radiation) do
|
|
82
|
- p = floor(chromosome.size * radiation)
|
|
83
|
- genes =
|
|
84
|
- if p == chromosome.size-1 do
|
|
85
|
- chromosome.genes
|
|
86
|
- |> Enum.reverse()
|
|
87
|
- else
|
|
88
|
- {head, tail} =
|
|
89
|
- chromosome.genes
|
|
90
|
- |> Enum.split(p)
|
|
91
|
- head
|
|
92
|
- |> Enum.reverse()
|
|
93
|
- |> Kernel.++(tail)
|
|
94
|
- end
|
|
99
|
+ chromosome_length = chromosome.size
|
|
100
|
+ point = if chromosome_length == 0, do: 0, else: :rand.uniform(chromosome_length)
|
|
101
|
+ num_to_invert = floor(radiation * chromosome_length)
|
|
102
|
+ invert(chromosome, point, point + num_to_invert)
|
|
103
|
+ end
|
|
104
|
+
|
|
105
|
+ def invert(_, _), do: raise(ArgumentError, message: "Invalid radiation level!")
|
|
106
|
+
|
|
107
|
+ @doc """
|
|
108
|
+ Perform inversion mutation on a known slice.
|
|
109
|
+
|
|
110
|
+ This mutation reverses (inverts) a known slice of genes of the Chromosome.
|
|
111
|
+
|
|
112
|
+ Returns `%Chromosome{}`.
|
|
113
|
+
|
|
114
|
+ # Parameters
|
|
115
|
+ - `chromosome`: `Chromosome` to mutate.
|
|
116
|
+ - `start`: Start of slice.
|
|
117
|
+ - `finish`: End of slice.
|
|
118
|
+
|
|
119
|
+ # Examples
|
|
120
|
+
|
|
121
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
122
|
+ iex> invert(c1, 2, 4)
|
|
123
|
+ %#{Chromosome}{genes: [1, 2, 4, 3, 5], size: 5}
|
|
124
|
+
|
|
125
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
126
|
+ iex> invert(c1, 10, 3)
|
|
127
|
+ %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
128
|
+
|
|
129
|
+ iex> c1 = %#{Chromosome}{genes: [1, 2, 3, 4, 5], size: 5}
|
|
130
|
+ iex> invert(c1, 0, 10)
|
|
131
|
+ %#{Chromosome}{genes: [5, 4, 3, 2, 1], size: 5}
|
|
132
|
+ """
|
|
133
|
+ @spec invert(Chromosome.t(), integer(), integer()) :: Chromosome.t()
|
|
134
|
+ def invert(chromosome, start, finish) do
|
|
135
|
+ {head, slice} = Enum.split(chromosome.genes, start)
|
|
136
|
+ {slice, tail} = Enum.split(slice, finish - start)
|
|
137
|
+ genes = head ++ Enum.reverse(slice) ++ tail
|
|
95
138
|
%Chromosome{chromosome | genes: genes}
|
|
96
139
|
end
|
|
97
|
- def invert(_, _), do: raise "Invalid radiation level!"
|
|
98
140
|
|
|
99
141
|
@doc """
|
|
100
142
|
Performs uniform integer mutation.
|
|
|
@@ -113,18 +155,18 @@ defmodule Genex.Operators.Mutation do
|
|
113
155
|
def uniform_integer(chromosome, radiation, min, max) when valid_rate?(radiation) do
|
|
114
156
|
genes =
|
|
115
157
|
chromosome.genes
|
|
116
|
- |> Enum.map(
|
|
117
|
- fn x ->
|
|
118
|
- if :rand.uniform() < radiation do
|
|
119
|
- Enum.random(min..max)
|
|
120
|
- else
|
|
121
|
- x
|
|
122
|
- end
|
|
123
|
- end
|
|
124
|
- )
|
|
158
|
+ |> Enum.map(fn x ->
|
|
159
|
+ if :rand.uniform() < radiation do
|
|
160
|
+ Enum.random(min..max)
|
|
161
|
+ else
|
|
162
|
+ x
|
|
163
|
+ end
|
|
164
|
+ end)
|
|
165
|
+
|
|
125
166
|
%Chromosome{chromosome | genes: genes}
|
|
126
167
|
end
|
|
127
|
- def uniform_integer(_, _, _, _), do: raise "Invalid radiation level!"
|
|
168
|
+
|
|
169
|
+ def uniform_integer(_, _, _, _), do: raise(ArgumentError, message: "Invalid radiation level!")
|
|
128
170
|
|
|
129
171
|
@doc """
|
|
130
172
|
Performs a gaussian mutation.
|
|
|
@@ -140,25 +182,28 @@ defmodule Genex.Operators.Mutation do
|
|
140
182
|
@spec gaussian(Chromosome.t(), float()) :: Chromosome.t()
|
|
141
183
|
def gaussian(chromosome, radiation) when valid_rate?(radiation) do
|
|
142
184
|
mu = Enum.sum(chromosome.genes) / length(chromosome.genes)
|
|
185
|
+
|
|
143
186
|
sigma =
|
|
144
187
|
chromosome.genes
|
|
145
188
|
|> Enum.map(fn x -> (mu - x) * (mu - x) end)
|
|
146
189
|
|> Enum.sum()
|
|
147
190
|
|> Kernel./(length(chromosome.genes))
|
|
191
|
+
|
|
148
192
|
genes =
|
|
149
193
|
chromosome.genes
|
|
150
|
- |> Enum.map(
|
|
151
|
- fn x ->
|
|
152
|
- if :rand.uniform() < radiation do
|
|
153
|
- :rand.normal(mu, sigma)
|
|
154
|
- else
|
|
155
|
- x
|
|
156
|
- end
|
|
157
|
- end
|
|
158
|
- )
|
|
194
|
+ |> Enum.map(fn x ->
|
|
195
|
+ if :rand.uniform() < radiation do
|
|
196
|
+ :rand.normal(mu, sigma)
|
|
197
|
+ else
|
|
198
|
+ x
|
|
199
|
+ end
|
|
200
|
+ end)
|
|
201
|
+
|
|
159
202
|
%Chromosome{chromosome | genes: genes}
|
|
160
203
|
end
|
|
161
204
|
|
|
205
|
+ def gaussian(_, _), do: raise(ArgumentError, "Invalid radiation level!")
|
|
206
|
+
|
|
162
207
|
@doc """
|
|
163
208
|
Performs Polynomial Bounded mutation.
|
|
164
209
|
|
|
|
@@ -176,30 +221,32 @@ defmodule Genex.Operators.Mutation do
|
|
176
221
|
def polynomial_bounded(chromosome, radiation, eta, low, high) when valid_rate?(radiation) do
|
|
177
222
|
genes =
|
|
178
223
|
chromosome.genes
|
|
179
|
- |> Enum.map(
|
|
180
|
- fn x ->
|
|
181
|
- delta_1 = (x - low) / (high - low)
|
|
182
|
- delta_2 = (high - x) / (high - low)
|
|
183
|
- rand = :rand.uniform()
|
|
184
|
- mut_pow = 1.0 / (eta + 1)
|
|
224
|
+ |> Enum.map(fn x ->
|
|
225
|
+ delta_1 = (x - low) / (high - low)
|
|
226
|
+ delta_2 = (high - x) / (high - low)
|
|
227
|
+ rand = :rand.uniform()
|
|
228
|
+ mut_pow = 1.0 / (eta + 1)
|
|
185
229
|
|
|
186
|
- delta_q =
|
|
187
|
- if rand < radiation do
|
|
188
|
- a = 1.0 - delta_1
|
|
189
|
- b = 2.0 * rand + (1.0 - 2.0 * rand) * :math.pow(a, eta+1)
|
|
190
|
- c = :math.pow(b, mut_pow - 1)
|
|
191
|
- c
|
|
192
|
- else
|
|
193
|
- a = 1.0 - delta_2
|
|
194
|
- b = 2.0 * rand + (1.0 - 2.0 * rand) * :math.pow(a, eta+1)
|
|
195
|
- c = 1.0 - :math.pow(b, mut_pow)
|
|
196
|
- c
|
|
197
|
- end
|
|
198
|
- y = x + delta_q * (high - low)
|
|
199
|
- min(max(y, low), high)
|
|
230
|
+ delta_q =
|
|
231
|
+ if rand < radiation do
|
|
232
|
+ a = 1.0 - delta_1
|
|
233
|
+ b = 2.0 * rand + (1.0 - 2.0 * rand) * :math.pow(a, eta + 1)
|
|
234
|
+ c = :math.pow(b, mut_pow - 1)
|
|
235
|
+ c
|
|
236
|
+ else
|
|
237
|
+ a = 1.0 - delta_2
|
|
238
|
+ b = 2.0 * rand + (1.0 - 2.0 * rand) * :math.pow(a, eta + 1)
|
|
239
|
+ c = 1.0 - :math.pow(b, mut_pow)
|
|
240
|
+ c
|
|
200
241
|
end
|
|
201
|
- )
|
|
242
|
+
|
|
243
|
+ y = x + delta_q * (high - low)
|
|
244
|
+ min(max(y, low), high)
|
|
245
|
+ end)
|
|
246
|
+
|
|
202
247
|
%Chromosome{chromosome | genes: genes}
|
|
203
248
|
end
|
|
204
|
- def polynomial_bounded(_, _, _, _, _), do: raise "Invalid radiation level!"
|
|
249
|
+
|
|
250
|
+ def polynomial_bounded(_, _, _, _, _),
|
|
251
|
+ do: raise(ArgumentError, message: "Invalid radiation level!")
|
|
205
252
|
end
|
changed
lib/genex/operators/selection.ex
|
|
@@ -38,7 +38,7 @@ defmodule Genex.Operators.Selection do
|
|
38
38
|
@spec worst(Enum.t(), integer()) :: Enum.t()
|
|
39
39
|
def worst(chromosomes, n) do
|
|
40
40
|
chromosomes
|
|
41
|
- |> Enum.reverse
|
|
41
|
+ |> Enum.reverse()
|
|
42
42
|
|> Enum.take(n)
|
|
43
43
|
end
|
|
44
44
|
|
|
|
@@ -73,14 +73,12 @@ defmodule Genex.Operators.Selection do
|
|
73
73
|
"""
|
|
74
74
|
@spec tournament(Enum.t(), integer(), integer()) :: Enum.t()
|
|
75
75
|
def tournament(chromosomes, n, tournsize) do
|
|
76
|
- 0..n-1
|
|
77
|
- |> Enum.map(
|
|
78
|
- fn _ ->
|
|
79
|
- chromosomes
|
|
80
|
- |> Enum.take_random(tournsize)
|
|
81
|
- |> Enum.max_by(&Genex.Chromosome.get_fitness/1)
|
|
82
|
- end
|
|
83
|
- )
|
|
76
|
+ 0..(n - 1)
|
|
77
|
+ |> Enum.map(fn _ ->
|
|
78
|
+ chromosomes
|
|
79
|
+ |> Enum.take_random(tournsize)
|
|
80
|
+ |> Enum.max_by(&Genex.Chromosome.get_fitness/1)
|
|
81
|
+ end)
|
|
84
82
|
end
|
|
85
83
|
|
|
86
84
|
@doc """
|
|
|
@@ -98,23 +96,24 @@ defmodule Genex.Operators.Selection do
|
|
98
96
|
def roulette(chromosomes, n) do
|
|
99
97
|
sum_fitness =
|
|
100
98
|
chromosomes
|
|
101
|
- |> Enum.reduce(0, fn x, acc -> acc+x.fitness end)
|
|
102
|
- 0..n-1
|
|
103
|
- |> Enum.map(
|
|
104
|
- fn _ ->
|
|
105
|
- u = :rand.uniform() * sum_fitness
|
|
106
|
- chromosomes
|
|
107
|
- |> Enum.reduce_while(0,
|
|
108
|
- fn x, sum ->
|
|
109
|
- if x.fitness+sum > u do
|
|
110
|
- {:halt, x}
|
|
111
|
- else
|
|
112
|
- {:cont, x.fitness+sum}
|
|
113
|
- end
|
|
114
|
- end
|
|
115
|
- )
|
|
99
|
+ |> Enum.reduce(0, fn x, acc -> acc + x.fitness end)
|
|
100
|
+
|
|
101
|
+ 0..(n - 1)
|
|
102
|
+ |> Enum.map(fn _ ->
|
|
103
|
+ u = :rand.uniform() * sum_fitness
|
|
104
|
+
|
|
105
|
+ chromosomes
|
|
106
|
+ |> Enum.reduce_while(
|
|
107
|
+ 0,
|
|
108
|
+ fn x, sum ->
|
|
109
|
+ if x.fitness + sum > u do
|
|
110
|
+ {:halt, x}
|
|
111
|
+ else
|
|
112
|
+ {:cont, x.fitness + sum}
|
|
113
|
+ end
|
|
116
114
|
end
|
|
117
115
|
)
|
|
116
|
+ end)
|
|
118
117
|
end
|
|
119
118
|
|
|
120
119
|
@doc """
|
|
|
@@ -132,24 +131,25 @@ defmodule Genex.Operators.Selection do
|
|
132
131
|
def stochastic_universal_sampling(chromosomes, n) do
|
|
133
132
|
sum_fitness =
|
|
134
133
|
chromosomes
|
|
135
|
- |> Enum.reduce(0, fn x, acc -> acc+x.fitness end)
|
|
134
|
+ |> Enum.reduce(0, fn x, acc -> acc + x.fitness end)
|
|
135
|
+
|
|
136
136
|
p = sum_fitness / n
|
|
137
137
|
start = p * :rand.uniform()
|
|
138
|
- pointers = for i <- 0..n-1, do: start + i*p
|
|
138
|
+ pointers = for i <- 0..(n - 1), do: start + i * p
|
|
139
|
+
|
|
139
140
|
pointers
|
|
140
|
- |> Enum.map(
|
|
141
|
- fn x ->
|
|
142
|
- chromosomes
|
|
143
|
- |> Enum.reduce_while(0,
|
|
144
|
- fn y, sum ->
|
|
145
|
- if y.fitness+sum >= x do
|
|
146
|
- {:halt, y}
|
|
147
|
- else
|
|
148
|
- {:cont, y.fitness+sum}
|
|
149
|
- end
|
|
150
|
- end
|
|
151
|
- )
|
|
141
|
+ |> Enum.map(fn x ->
|
|
142
|
+ chromosomes
|
|
143
|
+ |> Enum.reduce_while(
|
|
144
|
+ 0,
|
|
145
|
+ fn y, sum ->
|
|
146
|
+ if y.fitness + sum >= x do
|
|
147
|
+ {:halt, y}
|
|
148
|
+ else
|
|
149
|
+ {:cont, y.fitness + sum}
|
|
150
|
+ end
|
|
152
151
|
end
|
|
153
152
|
)
|
|
153
|
+ end)
|
|
154
154
|
end
|
|
155
155
|
end
|
changed
lib/genex/population.ex
|
|
@@ -1,5 +1,6 @@
|
|
1
1
|
defmodule Genex.Population do
|
|
2
2
|
alias Genex.Chromosome
|
|
3
|
+
|
|
3
4
|
@moduledoc """
|
|
4
5
|
A collection of `Chromosomes`.
|
|
5
6
|
|
|
|
@@ -9,17 +10,17 @@ defmodule Genex.Population do
|
|
9
10
|
"""
|
|
10
11
|
|
|
11
12
|
@type t :: %__MODULE__{
|
|
12
|
- chromosomes: Enum.t(),
|
|
13
|
- generation: integer(),
|
|
14
|
- max_fitness: number(),
|
|
15
|
- parents: Enum.t() | nil,
|
|
16
|
- survivors: Enum.t() | nil,
|
|
17
|
- children: Enum.t() | nil,
|
|
18
|
- size: integer(),
|
|
19
|
- strongest: Chromosome.t(),
|
|
20
|
- history: :digraph.graph(),
|
|
21
|
- statistics: Keyword.t()
|
|
22
|
- }
|
|
13
|
+ chromosomes: Enum.t(),
|
|
14
|
+ generation: integer(),
|
|
15
|
+ max_fitness: number(),
|
|
16
|
+ parents: Enum.t() | nil,
|
|
17
|
+ survivors: Enum.t() | nil,
|
|
18
|
+ children: Enum.t() | nil,
|
|
19
|
+ size: integer(),
|
|
20
|
+ strongest: Chromosome.t(),
|
|
21
|
+ history: :digraph.graph(),
|
|
22
|
+ statistics: Keyword.t()
|
|
23
|
+ }
|
|
23
24
|
|
|
24
25
|
@enforce_keys [:chromosomes]
|
|
25
26
|
defstruct [
|
|
|
@@ -43,6 +44,7 @@ defmodule Genex.Population do
|
|
43
44
|
population.chromosomes
|
|
44
45
|
|> Enum.sort_by(&Chromosome.get_fitness/1)
|
|
45
46
|
|> Enum.reverse()
|
|
47
|
+
|
|
46
48
|
%__MODULE__{population | chromosomes: sorted_chromosomes, strongest: hd(sorted_chromosomes)}
|
|
47
49
|
end
|
|
48
50
|
end
|
changed
lib/genex/support/genealogy.ex
|
|
@@ -10,7 +10,7 @@ defmodule Genex.Support.Genealogy do
|
|
10
10
|
|
|
11
11
|
Returns `Graph`.
|
|
12
12
|
"""
|
|
13
|
- def init, do: :digraph.new()
|
|
13
|
+ def init, do: Graph.new(type: :directed)
|
|
14
14
|
|
|
15
15
|
@doc """
|
|
16
16
|
Updates a Genealogy Tree with just a vertex.
|
|
|
@@ -22,25 +22,46 @@ defmodule Genex.Support.Genealogy do
|
|
22
22
|
- `chromosome` - Chromosome to add to Genealogy.
|
|
23
23
|
"""
|
|
24
24
|
def update(genealogy, chromosome) do
|
|
25
|
- :digraph.add_vertex(genealogy, chromosome)
|
|
26
25
|
genealogy
|
|
26
|
+ |> Graph.add_vertex(chromosome)
|
|
27
27
|
end
|
|
28
28
|
|
|
29
29
|
@doc """
|
|
30
|
- Updates a Genealogy Tree with a vertex and it's corresponding parents.
|
|
30
|
+ Updates a Genealogy Tree with a vertex and it's parents.
|
|
31
31
|
|
|
32
32
|
Returns `Graph`.
|
|
33
33
|
|
|
34
34
|
# Parameters
|
|
35
35
|
- `genealogy` - Reference to a Genealogy Tree.
|
|
36
|
- - `chromosome` - Chromosome to add to genealogy.
|
|
37
|
- - `parent_a` - Parent Chromosome.
|
|
38
|
- - `parent_b` - Parent Chromosome.
|
|
36
|
+ - `child` - Chromosome to add.
|
|
37
|
+ - `parent_a` - Child's parent.
|
|
38
|
+ - `parent_b` - Child's parent.
|
|
39
39
|
"""
|
|
40
|
- def update(genealogy, chromosome, parent_a, parent_b) do
|
|
41
|
- :digraph.add_vertex(genealogy, chromosome)
|
|
42
|
- :digraph.add_edge(genealogy, parent_a, chromosome)
|
|
43
|
- :digraph.add_edge(genealogy, parent_b, chromosome)
|
|
40
|
+ def update(genealogy, child, parent_a, parent_b) do
|
|
44
41
|
genealogy
|
|
42
|
+ |> Graph.add_vertex(child)
|
|
43
|
+ |> Graph.add_edge(parent_a, child)
|
|
44
|
+ |> Graph.add_edge(parent_b, child)
|
|
45
45
|
end
|
|
46
|
- end
|
|
|
\ No newline at end of file
|
|
46
|
+
|
|
47
|
+ @doc """
|
|
48
|
+ Add a generation of `Chromosomes` to Genealogy Tree.
|
|
49
|
+
|
|
50
|
+ Returns `Graph`.
|
|
51
|
+
|
|
52
|
+ # Parameters
|
|
53
|
+ - `genealogy` - Reference to a Genealogy tree.
|
|
54
|
+ - `chromosome` - Chromosome to add.
|
|
55
|
+ """
|
|
56
|
+ def add_generation(genealogy, chromosomes) do
|
|
57
|
+ Graph.add_vertices(genealogy, chromosomes)
|
|
58
|
+ end
|
|
59
|
+
|
|
60
|
+ @doc """
|
|
61
|
+ Exports the genealogy tree.
|
|
62
|
+ """
|
|
63
|
+ def export(genealogy) do
|
|
64
|
+ genealogy
|
|
65
|
+ |> Graph.Serializers.DOT.serialize()
|
|
66
|
+ end
|
|
67
|
+ end
|
changed
lib/genex/support/statistics.ex
|
|
@@ -3,22 +3,129 @@ defmodule Genex.Support.Statistics do
|
|
3
3
|
Provides basic summary statistics for use in the Population struct.
|
|
4
4
|
"""
|
|
5
5
|
|
|
6
|
+ @doc """
|
|
7
|
+ Takes the mean of `list`.
|
|
8
|
+
|
|
9
|
+ Returns `Number`.
|
|
10
|
+
|
|
11
|
+ # Parameters
|
|
12
|
+ - `list`: List of values.
|
|
13
|
+
|
|
14
|
+ # Examples
|
|
15
|
+
|
|
16
|
+ iex> list = [1, 2, 3, 4, 5]
|
|
17
|
+ iex> mean(list)
|
|
18
|
+ 3.0
|
|
19
|
+
|
|
20
|
+ iex> list = []
|
|
21
|
+ iex> mean(list)
|
|
22
|
+ 0
|
|
23
|
+ """
|
|
24
|
+ def mean([]), do: 0
|
|
25
|
+
|
|
6
26
|
def mean(list) do
|
|
7
27
|
list
|
|
8
28
|
|> Enum.sum()
|
|
9
29
|
|> Kernel./(length(list))
|
|
10
30
|
end
|
|
11
31
|
|
|
32
|
+ @doc """
|
|
33
|
+ Takes the variance of `list`.
|
|
34
|
+
|
|
35
|
+ Returns `Number`.
|
|
36
|
+
|
|
37
|
+ # Parameters
|
|
38
|
+ - `list`: List of values.
|
|
39
|
+
|
|
40
|
+ # Examples
|
|
41
|
+
|
|
42
|
+ iex> list = [0, 1, 1, 1]
|
|
43
|
+ iex> variance(list)
|
|
44
|
+ 0.25
|
|
45
|
+
|
|
46
|
+ iex> list = []
|
|
47
|
+ iex> variance(list)
|
|
48
|
+ 0
|
|
49
|
+ """
|
|
50
|
+ def variance([]), do: 0
|
|
51
|
+
|
|
12
52
|
def variance(list) do
|
|
13
|
- list_mean = mean(list)
|
|
14
|
- list |> Enum.map(fn x -> (list_mean - x) * (list_mean - x) end) |> mean
|
|
53
|
+ avg = mean(list)
|
|
54
|
+ size = length(list)
|
|
55
|
+
|
|
56
|
+ list
|
|
57
|
+ |> Enum.reduce(
|
|
58
|
+ 0,
|
|
59
|
+ fn x, total ->
|
|
60
|
+ total + :math.pow(x - avg, 2)
|
|
61
|
+ end
|
|
62
|
+ )
|
|
63
|
+ |> Kernel./(size - 1)
|
|
15
64
|
end
|
|
16
65
|
|
|
66
|
+ @doc """
|
|
67
|
+ Takes the standard deviation of `list`.
|
|
68
|
+
|
|
69
|
+ Returns `Number`.
|
|
70
|
+
|
|
71
|
+ # Parameters
|
|
72
|
+ - `list`: List of values.
|
|
73
|
+
|
|
74
|
+ # Examples
|
|
75
|
+
|
|
76
|
+ iex> list = [0, 1, 1, 1]
|
|
77
|
+ iex> stdev(list)
|
|
78
|
+ 0.5
|
|
79
|
+
|
|
80
|
+ iex> list = []
|
|
81
|
+ iex> stdev(list)
|
|
82
|
+ 0
|
|
83
|
+ """
|
|
84
|
+ def stdev([]), do: 0
|
|
85
|
+
|
|
17
86
|
def stdev(list) do
|
|
18
87
|
:math.sqrt(variance(list))
|
|
19
88
|
end
|
|
20
89
|
|
|
90
|
+ @doc """
|
|
91
|
+ Takes the min of `list`.
|
|
92
|
+
|
|
93
|
+ Returns `Number`.
|
|
94
|
+
|
|
95
|
+ # Parameters
|
|
96
|
+ - `list`: List of values.
|
|
97
|
+
|
|
98
|
+ # Examples
|
|
99
|
+
|
|
100
|
+ iex> list = [1, 2, 3, 4, 5]
|
|
101
|
+ iex> min(list)
|
|
102
|
+ 1
|
|
103
|
+
|
|
104
|
+ iex> list = []
|
|
105
|
+ iex> min(list)
|
|
106
|
+ nil
|
|
107
|
+ """
|
|
108
|
+ def min([]), do: nil
|
|
21
109
|
def min(list), do: Enum.min(list)
|
|
22
110
|
|
|
111
|
+ @doc """
|
|
112
|
+ Takes the max of `list`.
|
|
113
|
+
|
|
114
|
+ Returns `Number`.
|
|
115
|
+
|
|
116
|
+ # Parameters
|
|
117
|
+ - `list`: List of values.
|
|
118
|
+
|
|
119
|
+ # Examples
|
|
120
|
+
|
|
121
|
+ iex> list = [1, 2, 3, 4, 5]
|
|
122
|
+ iex> max(list)
|
|
123
|
+ 5
|
|
124
|
+
|
|
125
|
+ iex> list = []
|
|
126
|
+ iex> max(list)
|
|
127
|
+ nil
|
|
128
|
+ """
|
|
129
|
+ def max([]), do: nil
|
|
23
130
|
def max(list), do: Enum.max(list)
|
|
24
|
- end
|
|
|
\ No newline at end of file
|
|
131
|
+ end
|
changed
lib/genex/visualizers/text.ex
|
|
@@ -9,10 +9,12 @@ defmodule Genex.Visualizers.Text do
|
|
9
9
|
def init do
|
|
10
10
|
title = "Genetic Algorithm"
|
|
11
11
|
header = ["Generation", "Size", "Max Fitness", "Strongest"]
|
|
12
|
+
|
|
12
13
|
rows = [
|
|
13
14
|
[0, 0, 0, ""],
|
|
14
15
|
[0, 0, 0, ""]
|
|
15
16
|
]
|
|
17
|
+
|
|
16
18
|
IO.write(TableRex.quick_render!(rows, header, title))
|
|
17
19
|
end
|
|
18
20
|
|
|
|
@@ -22,8 +24,9 @@ defmodule Genex.Visualizers.Text do
|
|
22
24
|
def display_summary(population) do
|
|
23
25
|
title = "Genetic Algorithm"
|
|
24
26
|
header = ["Generation", "Size", "Max Fitness", "Strongest"]
|
|
27
|
+
|
|
25
28
|
rows = [
|
|
26
|
- [population.generation, population.size, population.max_fitness, population.strongest],
|
|
29
|
+ [population.generation, population.size, population.max_fitness, population.strongest]
|
|
27
30
|
]
|
|
28
31
|
|
|
29
32
|
IO.ANSI.cursor_up(7)
|
changed
mix.exs
|
|
@@ -1,7 +1,7 @@
|
|
1
1
|
defmodule Genex.MixProject do
|
|
2
2
|
use Mix.Project
|
|
3
3
|
|
|
4
|
- @version "0.1.4"
|
|
4
|
+ @version "0.2.0"
|
|
5
5
|
@url "https://www.github.com/seanmor5/genex"
|
|
6
6
|
@maintainers ["Sean Moriarity"]
|
|
7
7
|
|
|
|
@@ -27,7 +27,7 @@ defmodule Genex.MixProject do
|
|
27
27
|
"coveralls.detail": :test,
|
|
28
28
|
"coveralls.post": :test,
|
|
29
29
|
"coveralls.html": :test
|
|
30
|
- ],
|
|
30
|
+ ]
|
|
31
31
|
]
|
|
32
32
|
end
|
|
33
33
|
|
|
|
@@ -74,6 +74,12 @@ defmodule Genex.MixProject do
|
|
74
74
|
],
|
|
75
75
|
"guides/support/benchmarking.md": [
|
|
76
76
|
filename: "support-benchmarking"
|
|
77
|
+ ],
|
|
78
|
+ "guides/support/genealogy.md": [
|
|
79
|
+ filename: "support-genealogy"
|
|
80
|
+ ],
|
|
81
|
+ "guides/operators/crossover.md": [
|
|
82
|
+ filename: "operators-crossover"
|
|
77
83
|
]
|
|
78
84
|
]
|
|
79
85
|
end
|
|
|
@@ -82,7 +88,8 @@ defmodule Genex.MixProject do
|
|
82
88
|
[
|
|
83
89
|
Introduction: Path.wildcard("guides/introduction/*.md"),
|
|
84
90
|
Support: Path.wildcard("guides/support/*.md"),
|
|
85
|
- Tutorials: Path.wildcard("guides/tutorials/*.md")
|
|
91
|
+ Tutorials: Path.wildcard("guides/tutorials/*.md"),
|
|
92
|
+ Operators: Path.wildcard("guides/operators/*.md")
|
|
86
93
|
]
|
|
87
94
|
end
|
|
88
95
|
|
|
|
@@ -93,11 +100,9 @@ defmodule Genex.MixProject do
|
|
93
100
|
Genex.Operators.Mutation,
|
|
94
101
|
Genex.Operators.Selection
|
|
95
102
|
],
|
|
96
|
-
|
|
97
103
|
Support: [
|
|
98
104
|
Genex.Support.Genealogy
|
|
99
105
|
],
|
|
100
|
-
|
|
101
106
|
Structures: [
|
|
102
107
|
Genex.Population,
|
|
103
108
|
Genex.Chromosome
|
|
|
@@ -111,7 +116,8 @@ defmodule Genex.MixProject do
|
|
111
116
|
{:ex_doc, "~> 0.21", only: :dev, runtime: false},
|
|
112
117
|
{:excoveralls, "~> 0.10", only: :test},
|
|
113
118
|
{:table_rex, "~> 2.0.0"},
|
|
114
|
- {:benchee, "~> 1.0"}
|
|
119
|
+ {:benchee, "~> 1.0"},
|
|
120
|
+ {:libgraph, "~> 0.13.0"}
|
|
115
121
|
]
|
|
116
122
|
end
|