Maths stuff not directly related  to Particle Swarm Optimization

Description Download Last Update
Hypersphere How to put random points inside a D-dimension hypersphere (not so easy). How to compute the volume of a hypersphere, and, more generally, how to compute the volume of the intersection of two hyperspheres  spherical_distribution


LCP to TSP How to explicitely transform a List Coloring problem into a Traveling Salesman Problem (method initially designed for Frequency Assignment Problem). A paper explaining the method

and a C program (zip file)
WARNING 2012-11: This zip file is corrupted. I don't have the original one anymore. If someone has it, or can repair the zip, please keep me posted

MasterMind 4 positions, 6 colors. An exhaustive  Excel analysis and an unbeatable small C program. spreadsheet and C source code (.zip) 2001-11-07
Constraint free binary coding of permutations
To transform any permutation problem into a binary one, without adding any constraints. Useful for optimisation.
C source code
Random permutation generation
An uniform pseudo-random generator of permutations. Most of the others are in fact biased.
C source code
Collective decision, or When minority wins
At the beginning, very few people do have an opinion.
At each time step, each guy who has an opinion says it to a few number of others, at random.
Each guy who receives an opinion adopts it, with a probability pr.
Even for pr<0.5, after a while, everybody has the same opinion ...
C source code
Comparing algorithms
How to compare two stochastic algorithms, knowing their results on a benchmark set of problems? Here is an user point of view
PDF file
Zipped XLS file
Permutations generator
Classical but useful: generates either the N! permutations of {1,2,..,N}, or just the (N-1)! "cycles"
SciLab recursive source code
Permutation coding/decoding
Code a permutation into an integer. Decode an integer into a permutation. Methods coming from Mersenne (~1630) and Laisant (1888). The last version can cope with big integers, by "splitting" them
C code
C code
Hammersley Generation of N points in a D-parallelepid. Classical Hammersley method, and an improved variant. See also below Quasi-random number generation.
C code 2008-11-22
Variograms and kriging For any defined function, compute a variogram and the corresponding kriging coefficients C code 2009-03-05
Universal Random Number Generator
A tool  to generate random numbers according to any probability distribution
Explanation + C code (PDF file)
A tool to solve dense linear systems.  For square systems, but may be easily adapted. Four methods, including my own substitution method, better than the Gauss-Seidel one
C Code
Random rotation
Generate the matrix of a random rotation in dimension D. May also generate the matrix of the inverse rotation. As it is a recursive program, it may not work with some compilers
C code
Given an integer position, find the nearest one with all components different. May be useful for combinatorial optimisation
C code, simplified version of the one that is used in Tribes C
Exclusive Rand
Given N elements, choose at random n of them, so that they are all different. Maybe useful for instance for Differential Evolution
C code (zipped)
Quasi-random numbers generation
Generate Sobol or Halton sequences in [0,1]^D
C code + two graphs (zipped)
Intersection sphere-cube or sphere-sphere
Relative volume of the intersection of a sphere S and a cube (or a sphere) centered on the surface of S.
C code + two graphs (zipped)
Biased RNG
Generation of biased "random" numbers, according to a psychological law
C code (zipped)
In a D-cube, generate smaller D-cubes "around" a center.
This may be useful for some optimisation methods, which have to define areas
to avoid, or, on the contrary, to more finely explore.
C code
Determinant of a square matrix
Not new, but I needed it for a "Nelder-Mead method revisited". So, it may be useful for some other people
C code (zipped)
Volume of a simplex
Same remark
C code (zipped)
Intrinsic difficulty
A small theoretical study about the intrinsic difficulty of optimisation problems. Apparently completely useless, but who knows? ;-)
Combinatorial tools A set of useful tools to manipulate permutations. In particular, finding a minimum list of transpositions to "go" from a permutation to another one. Scilab codes