For every constraint handling method 100 optimization procedures were performed with random initial configurations. The proved optimal packing density is (5-sqrt(5))/3 ~  0.921310674166737

Penalty function based on feasibility

I used the penalty function from this paper:  An efficient constraint handling method for genetic algorithms

The closest the algorithm got to the optimum was  0.921310674166735 in 2 instances with the constraint violation of 1.110223024625157e-16. This is also the minimum constraint violation achieved in 100 runs. This same value of constraint violation had 53 other instances with mean 0.921310674166652 and variance 2.276453802275327e-25.

The overall mean density from the 100 runs was 0.8926 and variance 0.0061.

In 99 instances the output solution violated constrains. In these cases the mean of constraint violation was 0.002671273212076 and variance 1.732259359382852e-04.

Dynamic penalty

I’ve tested the dynamic penalty function from: A survey of constraint handling techniques used with evolutionary algorithms

In 100 experiments all of the output solution violated the constraints. the minimum constrain violation in these 100 instances was 0.8888 and mean constraint violation 1.5547. This is very bad.

An interesting observation is that when I replaced the values of the objective function with the maximum of feasible solutions (as in Penalty function based on feasibility) in the penalty function the algorithm suddenly performed very well.

Annealing penalty

Same case as with dynamic penalty.

Death penalty

Not really good. Gets stuck in configurations where it can’t find any feasible samples very quickly.

Repair

Very slow and not very precise due to the way the repairing is implemented. That is by multiplying the unit cell by a small constant c>1 until there is no overlap.

Augmented lagrangian method

I’ve implemented the augmented lagrangian method for the xNES from this paper:  Augmented Lagrangian Genetic Algorithm for Structural Optimization

Same as in the case of dynamic penalties. All of the 100 experiments outpu solutions violated the constraints. The mean constraint violation was 1.0899 with variance 0.0020. Not useful at all.

Augmented lagrangian method with penalty function based on feasibility

In 45 cases the algorithms  output solution’s nonlinear constrains were distanced from zero less then 1.110223024625157e-16. Out of these 32 were unfeasible. From the feasible solutions the maximum density was 0.921310674166734 and the constraint violation of 0. Below is a picture of this solution.

The mean density of these 45 cases was 0.9205 and variance 2.0456e-05. Overall the mean density was 0.8777 and variance 0.0107. In 79 cases the constraints were violated. with mean constraint violation of 0.0017 and variance 6.7180e-05.

Slides: CMOpresentation.pdf

First experiments with packing pentagons using plane groups. Genetic algorithm was used to optimize the packing density.  It seems that the  optimal packing density is approx. 0.92 ( Packings of Regular Pentagons in the Plane ).

2. Plane group: p2

Density:  0.8550

3. Plane group: pm

Density:  0.6798

4. Plane group: pg

Density:  0.8879

5. Plane group: cm

Density:  0.7450

6. Plane group: p2mm

Density:  0.6930

7. Plane group: p2mg

Density:  0.8539

8. Plane group: p2gg

Density:  0.9104

9. Plane group: c2mm

Density:  0.6908

10. Plane group: p4

Density:  0.8423

11. Plane group: p4mm

Density:  0.5406

 

12. Plane group: p4gm

Density:  0.6957

13. Plane group: p3

Density:  0.8578

14. Plane group: p3m1

Density:  0.5236

15. Plane group: p31m

Density:  0.6980

16. Plane group: p6

Density:  0.7290

17. Plane group: p6mm

Density:  0.4914

Slides: miloPresentation.pdf

Slides: endOfYearPresentation.pdf

Starting to experiment with combinatorial packings by gluing particles together along their edges and finding a configuration with maximal ratio between the volume of the sum of the particles and the volume of the convex hull of the particles. Here are some examples.

ratio = 0.4500

Expanding the tree to two particles. There are only two admissible configurations with different  ratios for two particles.

1. branch

ratio = 0.4

Ratios from left to right: 0.3857,  0.4045,  04075, 0.4372,  0.4015,  0.3724

 

2. branch

ratio = 0.4091

Ratios from left to right: 0.4045,  0.3971, 0.3803, 0.4075,  0.4372,  0.4015

Just to have everything in one place.

MiloslavTorda_FirstYearReport.pdf

I modified the original algorithm to work better. It’s significantly slower but I get better results. There seems to be a relationship between number of objects in the unit cell and the algorithm’s performance. The  more shapes the worse density. (more local minima on the landscape?). The other thing is packings are physically unrealistic, that is the shapes from different unit cells are intertwined. No more problem is that the density did go higher then 1 which should not be.  Maybe we need a more suitable formula for computing density in the periodic setting.

Results

1 pentacene model in a unit cell

Density = 1.9932

 

2 pentacene models in a unit cell

Density = 1.0063

4 pentacene models in a unit cell

Density = 0.8093

8 pentacene models in a unit cell

Density = 0.6940

54 pentacene models in a unit cell

Density = 0.1788

I got to packing Pentacene model  based on previous computations. see http://milotorda.net/index.php/pentacene-modeling/    . From the coordinates of the atoms of the Pentacene molecule

I have created a point cloud by placing 14 points around every atom in the Pentacene uniformly placed on a sphere with radius 0.5573/2.

and finally taken the convex hull of the point cloud as the 3D-model of Pentacene. The resulting structure is in the form of triangulation with 58 vertices, 112 edges and 168 faces. Volume of the polyhedron is 48.237.

Subsequently I used the Torquato – Jiao packing algorithm to create packings of various numbers of pentacene models in a unit cell.

4 pentacene models in a unit cell

Initial configuration

Density = 0.0037.

Original algorithm

First iteration

Density = 0.0291

Second iteration

Density = 0.0512

simulated annealing

First iteration

Density = 0.0514

Second iteration

Density = 0.1178

8 pentacene models in a unit cell

initial configuration

Density = 0.0075

Original algorithm

First iteration

Density = 0.0660

Second iteration

Density = 0.0436

simulated annealing

First iteration

Density = 0.0234

I experimented with the packing of triangles using previous model and Matlab’s fmincon() optimizer. For each setting 100 runs were performed with the following initial conditions. Triangles have  the same initial positions in the initial unit cell with random rotations. The algorithm used was interior point with supplied objective gradient.

3 triangle setting

Out of 100 runs 45 resulted in feasible solutions. 40 with exitflag== -2, 0 with exitflag== -1, 21 with exitflag== 0., 0 with exitflag== 1,  39 with exitflag== 2.  Mean density in the feasible solution cases was 0.5827 and variance 0.0197. The best case had density 0.8118.

Left is the initial setup and right is the best found solution.

 

4 triangle setting

Out of 100 runs 20 resulted in feasible solutions. 66 with exitflag== -2, 0 with exitflag== -1,  14 with exitflag== 0., 0 with exitflag== 1,  20 with exitflag== 2.  Mean density in the feasible solution cases was 0.5850 and variance  0.0127. The best case had density  0.7959.

Left is the initial setup and right is the best found solution.

5 triangle setting

Out of 100 runs 9 resulted in feasible solutions. 71 with exitflag== -2, 0 with exitflag== -1,  20 with exitflag== 0., 0 with exitflag== 1,  9 with exitflag== 2.  Mean density in the feasible solution cases was 0.5637 and variance  0.0111. The best case had density  0.7246.

Left is the initial setup and right is the best found solution.

 

4 triangle setting and GA

I did similiar thing with the GA algorithm. Out of 49 runs 19 resulted in feasible solutions.  Mean density in the feasible solution cases was 0.7667 and variance  0.0115. The best case had density  0.9230.