#include
#include
#include
#include
#include
#include
#include "tree/ytree.h"
#include "input.h"
int DATA_COUNT;
/**
* sufficient_k()
* ``````````````
* @n : Number of leaf nodes in the phylogenetic tree
* Return: Minimum k allowing complete mutation.
*
* NOTE
* For the class {T} of phylogenetic trees with n leaf nodes,
* this function returns the minimal k such that for an
* arbitrary tree t in {T}, there exists a k-mutation which
* can transform t into arbitrary t' also in {T}.
*
* That is, given at least k mutations, any tree in the class
* can be transformed into any other tree also in the class.
*/
static inline int sufficient_k(int n)
{
return (5 * n) - 16;
}
/**
* build_pmf()
* -----------
* Construct the probability mass function for the alias.
*
* @limit: Maximum value to sample in the distribution
* Return: Array of probability values, suitable for building an alias.
*
* NOTE
* The actual distribution being used is from [1], namely,
*
* p(k) = 1 / ( (k+2) * (log(k+2)^2) ).
*
* This is a shifted version of the more general equation
*
* p(k) = c / ( (k) * (log(k)^2) ),
*
* with c ~= 2.1.
*
* Among the family of smooth analytic functions that can be expressed
* as a series of fractional powers and logarithms, this equation lies
* on the exact edge of the convergence zone.
*
* SUM(1/k)
* SUM(1/(k*log(k)) ----\ divergent
* SUM(1/(k*log(k)*log(log(k))) ----/ functions
*
* SUM(1/k^2)
* SUM(1/(k*(log(k)^2))) ----\ convergent
* SUM(1/(k*(log(k)*(log(k)^2)))) ----/ functions
*
* The probabilities of a discrete probability distribution must sum to 1,
* so any function used to describe the distribution must converge as k goes
* to infinity.
*
* 1/(k*(log(k)^2)) is thus one of the maximal "fat tail" distributions that
* exists. This will concentrate probability on larger values of k, which is
* what we want for constructing k-mutations.
*/
float *build_pmf(int limit)
{
float *value; /* value array */
float k; /* index */
float p; /* sum of probabilities */
value = calloc(limit, sizeof(float));
p = 0.0;
for (k=1; k best_cost || i == 0) {
best_cost = init_cost[i];
best_tree = tree[i];
}
}
champion = ytree_copy(best_tree);
/*
* Hill-climb for the optimal cost by
* mutating the existing tree according
* to the non-uniform probability given
* in the alias.
*/
for (i=0; i best_cost) {
best_cost = this_cost[j];
best_tree = tree[j];
}
}
if (best_tree != NULL) {
ytree_free(champion);
champion = ytree_copy(best_tree);
best_tree = NULL;
}
if (best_cost == 1.0) {
/* Halt */
break;
}
}
ynode_print(champion->root, "%d");
printf("best:%f init:", best_cost);
for (i=0; i | %s <# generations>", argv[0]);
}
return 0;
}