8000 Formatted all code google style · DontFearAlgorithms/Algorithms-1@f674f5f · GitHub
[go: up one dir, main page]
Skip to content

Commit f674f5f

Browse files
williamfisetwilliamfiset
committed
Formatted all code google style
1 parent e99d770 commit f674f5f

File tree

169 files changed

+4225
-5876
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

169 files changed

+4225
-5876
lines changed

‎build.gradle

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,17 @@
11

22
apply plugin: 'java'
3+
apply plugin: "com.github.sherter.google-java-format"
4+
5+
buildscript {
6+
repositories {
7+
maven {
8+
url "https://plugins.gradle.org/m2/"
9+
}
10+
}
11+
dependencies {
12+
classpath "gradle.plugin.com.github.sherter.google-java-format:google-java-format-gradle-plugin:0.8"
13+
}
14+
}
315

416
// Assume Java 8
517
sourceCompatibility = 1.8

‎com/williamfiset/algorithms/ai/GeneticAlgorithm_knapsack_01.java

Lines changed: 74 additions & 96 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,26 @@
11
/**
2-
* This file shows you how to attack the 0/1 knapsack problem using
3-
* an evolutionary genetic algorithm. The reason why we are interested
4-
* in doing this is because the dynamic programming approach to knapsack
5-
* only runs in pseudo polynomial time and fails terribly with large weight
2+
* This file shows you how to attack the 0/1 knapsack problem using an evolutionary genetic
3+
* algorithm. The reason why we are interested in doing this is because the dynamic programming
4+
* approach to knapsack only runs in pseudo polynomial time and fails terribly with large weight
65
* values, hence an approximation to the real answer would be nice.
76
*
87
* @author William Fiset, william.alexandre.fiset@gmail.com
9-
**/
8+
*/
109
package com.williamfiset.algorithms.ai;
1110

1211
import java.util.*;
1312

1413
public class GeneticAlgorithm_knapsack_01 {
15-
16-
final static Random RANDOM = new Random();
14+
15+
static final Random RANDOM = new Random();
1716

1817
// Genetic algorithm parameters (P = Population)
19-
final static int P = 500;
20-
final static int MAX_EPOCH = 10000;
21-
final static double MUTATION_RATE = 0.0125;
18+
static final int P = 500;
19+
static final int MAX_EPOCH = 10000;
20+
static final double MUTATION_RATE = 0.0125;
2221

23-
// The power variable tweaks the weight of the fitness function
24-
// to emphasize better individuals. The power slowly increments
22+
// The power variable tweaks the weight of the fitness function
23+
// to emphasize better individuals. The power slowly increments
2524
// over time to help get out of local minimums in later epochs.
2625
static double power;
2726
static final double POWER_INC = 0.0001;
@@ -34,26 +33,26 @@ static long run(int capacity, int[] weights, int[] values) {
3433
final int N = weights.length;
3534

3635
// Create initial population
37-
Individual[] generation = new Individual[P+1];
38-
Individual[] nextGeneration = new Individual[P+1];
39-
for(int i = 1; i <= P; i++) generation[i] = new Individual(N);
36+
Individual[] generation = new Individual[P + 1];
37+
Individual[] nextGeneration = new Individual[P + 1];
38+
for (int i = 1; i <= P; i++) generation[i] = new Individual(N);
4039

4140
// Stores the ranges of individuals in the selection roulette
42-
double [] lo = new double[P+1];
43-
double [] hi = new double[P+1];
41+
double[] lo = new double[P + 1];
42+
double[] hi = new double[P + 1];
4443

45-
long[] fitness = new long[P+1];
44+
long[] fitness = new long[P + 1];
4645
long bestFitness = 0;
4746

48-
for(int epoch = 1; epoch <= MAX_EPOCH; epoch++, power += POWER_INC) {
47+
for (int epoch = 1; epoch <= MAX_EPOCH; epoch++, power += POWER_INC) {
4948

5049
// Compute the total fitness sum across all individuals in order
5150
// to be able to normalize and assign importance percentages
5251
double fitnessSum = 0;
5352

54-
for(int i = 1; i <= P; i++) {
53+
for (int i = 1; i <= P; i++) {
5554
Individual in = generation[i];
56-
fitness[i] = fitness(in, weights,values, capacity, N);
55+
fitness[i] = fitness(in, weights, values, capacity, N);
5756
fitnessSum += fitness[i];
5857
lo[i] = hi[i] = 0;
5958
}
@@ -67,44 +66,36 @@ static long run(int capacity, int[] weights, int[] values) {
6766
Individual in = generation[i];
6867
double norm = fitness[i] / fitnessSum;
6968

70-
lo[i] = hi[i-1] = lo[i-1] + norm;
69+
lo[i] = hi[i - 1] = lo[i - 1] + norm;
7170

7271
if (fitness[i] > bestEpochFitness) {
7372
bestEpochFitness = fitness[i];
74-
if (bestEpochFitness > bestFitness)
75-
bestFitness = bestEpochFitness;
73+
if (bestEpochFitness > bestFitness) bestFitness = bestEpochFitness;
7674
}
77-
7875
}
7976

80-
81-
if (epoch % 50 == 0) System.out.printf("Epoch: %d, %d$, %d$\n", epoch, bestEpochFitness, bestFitness );
82-
77+
if (epoch % 50 == 0)
78+
System.out.printf("Epoch: %d, %d$, %d$\n", epoch, bestEpochFitness, bestFitness);
8379

8480
// Selection process
8581
for (int i = 1; i <= P; i++) {
86-
87-
// Perform individual selection and crossover
82+
83+
// Perform individual selection and crossover
8884
Individual parent1 = selectIndividual(generation, lo, hi);
8985
Individual parent2 = selectIndividual(generation, lo, hi);
90-
Individual child = crossover(parent1, parent2, N);
91-
92-
// Apply mutations to all parts of the DNA
86+
Individual child = crossover(parent1, parent2, N);
87+
88+
// Apply mutations to all parts of the DNA
9389
// according to a predefined mutation rate
94-
for(int j = 0; j < N; j++)
95-
if (Math.random() < MUTATION_RATE)
96-
mutate(child, j);
90+
for (int j = 0; j < N; j++) if (Math.random() < MUTATION_RATE) mutate(child, j);
9791

9892
nextGeneration[i] = child;
99-
10093
}
10194

10295
generation = nextGeneration;
103-
10496
}
10597

10698
return bestFitness;
107-
10899
}
109100

110101
static long fitness(Individual in, int[] weights, int[] values, int capacity, int n) {
@@ -123,47 +114,39 @@ static void mutate(Individual in, int i) {
123114
in.bits.flip(i);
124115
}
125116

126-
static Individual selectIndividual(Individual[] generation, double [] lo, double[] hi) {
127-
117+
static Individual selectIndividual(Individual[] generation, double[] lo, double[] hi) {
118+
128119
double r = Math.random();
129-
120+
130121
// Binary search to find individual
131-
int mid, l = 0, h = P-1;
122+
int mid, l = 0, h = P - 1;
132123
while (true) {
133124
mid = (l + h) >>> 1;
134-
if (lo[mid] <= r && r < hi[mid])
135-
return generation[mid+1];
136-
if (r < lo[mid])
137-
h = mid-1;
138-
else
139-
l = mid+1;
125+
if (lo[mid] <= r && r < hi[mid]) return generation[mid + 1];
126+
if (r < lo[mid]) h = mid - 1;
127+
else l = mid + 1;
140128
}
141-
142129
}
143130

144131
static Individual crossover(Individual p1, Individual p2, int n) {
145132
int splitPoint = RANDOM.nextInt(n);
146133
BitSet newBitSet = new BitSet(n);
147-
for(int i = 0; i < splitPoint; i++)
148-
if (p1.bits.get(i))
149-
newBitSet.flip(i);
150-
for(int i = splitPoint; i < n; i++)
151-
if (p2.bits.get(i))
152-
newBitSet.flip(i);
134+
for (int i = 0; i < splitPoint; i++) if (p1.bits.get(i)) newBitSet.flip(i);
135+
for (int i = splitPoint; i < n; i++) if (p2.bits.get(i)) newBitSet.flip(i);
153136
return new Individual(newBitSet);
154137
}
155138

156139
public static void main(String[] args) {
157-
140+
158141
int n = 50;
159142
int multiplier = 100000;
160143

161-
int [] weights = new int[n];
162-
int [] values = new int[n];
163-
144+
int[] weights = new int[n];
145+
int[] values = new int[n];
146+
164147
for (int i = 0; i < n; i++) {
165-
weights[i] = (int)(Math.random()*multiplier);
166-
values[i] = (int)(Math.random()*multiplier);
148+
weights[i] = (int) (Math.random() * multiplier);
149+
values[i] = (int) (Math.random() * multiplier);
167150
}
168151

169152
int cap = (n * multiplier) / 3;
@@ -172,14 +155,15 @@ public static void main(String[] args) {
172155

173156
System.out.println("\nGenetic algorithm approximation: " + gaAns + "$");
174157
System.out.println("Actual answer calculated with DP: " + answer + "$\n");
175-
System.out.printf("Genetic algorithm was %.5f%% off from true answer\n\n", (1.0 - ((double)gaAns)/answer) * 100 );
176-
158+
System.out.printf(
159+
"Genetic algorithm was %.5f%% off from true answer\n\n",
160+
(1.0 - ((double) gaAns) / answer) * 100);
177161
}
178-
162+
179163
static class Individual {
180-
164+
181165
BitSet bits;
182-
166+
183167
// Constructs a random individual
184168
public Individual(int n) {
185169
bits = new BitSet(n);
@@ -194,56 +178,50 @@ public Individual(BitSet set) {
194178
this.bits = set;
195179
}
196180

197-
@Override public String toString() {
181+
@Override
182+
public String toString() {
198183
return bits.toString();
199184
}
200-
201185
}
202186

203187
static class Knapsack_01 {
204-
188+
205189
/**
206190
* @param maxWeight - The maximum weight of the knapsack
207191
* @param W - The weights of the items
208192
* @param V - The values of the items
209-
* @return The maximum achievable profit of selecting a subset of
210-
* the elements such that the capacity of the knapsack is not exceeded
211-
**/
212-
public static int knapsack(int maxWeight, int [] W, int [] V) {
213-
214-
if (W == null || V == null || W.length != V.length || maxWeight < 0)
193+
* @return The maximum achievable profit of selecting a subset of the elements such that the
194+
* capacity of the knapsack is not exceeded
195+
*/
196+
public static int knapsack(int maxWeight, int[] W, int[] V) {
197+
198+
if (W == null || V == null || W.length != V.length || maxWeight < 0)
215199
throw new IllegalArgumentException("Invalid input");
216-
200+
217201
final int N = W.length;
218-
219-
// Initialize a table where individual rows represent items
202+
203+
// Initialize a table where individual rows represent items
220204
// and columns represent the weight of the knapsack
221-
int[][] DP = new int[N+1][maxWeight+1];
222-
205+
int[][] DP = new int[N + 1][maxWeight + 1];
206+
223207
for (int i = 1; i <= N; i++) {
224-
208+
225209
// Get the value and weight of the item
226-
int w = W[i-1], v = V[i-1];
227-
210+
int w = W[i - 1], v = V[i - 1];
211+
228212
for (int sz = 1; sz <= maxWeight; sz++) {
229-
213+
230214
// Consider not picking this element
231-
DP[i][sz] = DP[i-1][sz];
232-
215+
DP[i][sz] = DP[i - 1][sz];
216+
233217
// Consider including the current element and
234218
// see if this would be more profitable
235-
if (sz >= w && DP[i-1][sz-w] + v > DP[i][sz])
236-
DP[i][sz] = DP[i-1][sz-w] + v;
237-
219+
if (sz >= w && DP[i - 1][sz - w] + v > DP[i][sz]) DP[i][sz] = DP[i - 1][sz - w] + v;
238220
}
239-
240221
}
241-
222+
242223
// Return the maximum profit
243224
return DP[N][maxWeight];
244-
245225
}
246-
247226
}
248-
249-
}
227+
}

0 commit comments

Comments
 (0)
0