Du kan inte välja fler än 25 ämnen Ämnen måste starta med en bokstav eller siffra, kan innehålla bindestreck ('-') och vara max 35 tecken långa.

main.c 7.4KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361
  1. #include <assert.h>
  2. #include <math.h>
  3. #include <stdbool.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include <time.h>
  8. #include <unistd.h>
  9. #ifdef _WIN32
  10. # include <windows.h>
  11. #endif /* _WIN32 */
  12. #include "benchmark-data.h"
  13. /* Types */
  14. typedef int *solution;
  15. /* Functions */
  16. double distance(const vector u, const vector v);
  17. bool trouver_solution_initiale(void);
  18. bool solution_valide(const solution s);
  19. void print_solution(const solution s, const char *name);
  20. vector *centres_gravite(const solution s);
  21. int solution_voisine(solution *dest, const solution src);
  22. double fonction_objective(const solution s, double *inter, double *intra);
  23. static double calculer_inter(const vector *cgs);
  24. static double calculer_intra(const solution s, const vector *cgs);
  25. /* Variables */
  26. solution solution_opt;
  27. solution new_solution;
  28. int n_clusters = 5;
  29. int n_iterations = 1000;
  30. long double percentage = 10.0;
  31. int main(int argc, char *argv[])
  32. {
  33. int c;
  34. int i;
  35. double f0, inter, intra;;
  36. #ifdef _WIN32
  37. SetConsoleOutputCP(CP_UTF8);
  38. #endif /* _WIN32 */
  39. while ((c = getopt(argc, argv, ":c:i:p:h")) != -1) {
  40. int k;
  41. switch (c) {
  42. case 'c':
  43. k = atoi(optarg);
  44. if (k > 1)
  45. n_clusters = k;
  46. break;
  47. case 'i':
  48. k = atoi(optarg);
  49. if (k > 0)
  50. n_iterations = k;
  51. break;
  52. case 'p':
  53. {
  54. char *endp;
  55. long double p = strtold(optarg, &endp);
  56. if (p == 0.0 || *endp != '\0') {
  57. fprintf(stderr, "%s: Invalid percentage: %s\n", argv[0], optarg);
  58. exit(EXIT_FAILURE);
  59. }
  60. percentage = p;
  61. }
  62. break;
  63. case 'h':
  64. printf("Usage: %s [-c N_CLUSTERS] [-i N_ITERATIONS] [-p PERCENTAGE]", argv[0]);
  65. exit(EXIT_SUCCESS);
  66. break;
  67. default:
  68. exit(EXIT_FAILURE);
  69. }
  70. }
  71. printf("Using %d clusters\n", n_clusters);
  72. /* Init benchmark_data */
  73. init_benchmark_data();
  74. srand(time(NULL));
  75. if (!(solution_opt = calloc(N_VECTORS, sizeof(solution_opt[0]))))
  76. abort();
  77. /* Solution initiale */
  78. while (!trouver_solution_initiale())
  79. continue; /* do it again */
  80. f0 = fonction_objective(solution_opt, &inter, &intra);
  81. print_solution(solution_opt, "Solution initiale");
  82. printf("F = %f - %f = %f\n", inter, intra, f0);
  83. for (i = 0; i < n_iterations; i++) {
  84. double f1;
  85. while (!solution_voisine(&new_solution, solution_opt))
  86. continue; /* do it again */
  87. if ((f1 = fonction_objective(new_solution, &inter, &intra)) > f0) {
  88. print_solution(new_solution, "Nouvelle solution optimale trouvée");
  89. printf("F = %f - %f = %f (amélioration de %f%% par rapport à la dernière solution %f)\n",
  90. inter, intra, f1, fabs((f1 - f0) / f0 * 100.0), f0);
  91. free(solution_opt);
  92. solution_opt = new_solution;
  93. new_solution = NULL;
  94. f0 = f1;
  95. }
  96. }
  97. /* Free solution data */
  98. free(solution_opt);
  99. free(new_solution);
  100. /* Free benchmark data */
  101. for (i = 0; i < (int) N_VECTORS; i++)
  102. free(benchmark_data[i]);
  103. free(benchmark_data);
  104. exit(EXIT_SUCCESS);
  105. }
  106. double distance(const vector u, const vector v)
  107. {
  108. size_t i = 0;
  109. double sum = 0.0;
  110. if (!u || !v) {
  111. fputs("distance(): u or v is null.\n", stderr);
  112. abort();
  113. }
  114. /* d(u, v) = sqrt( (u1 - v1)^2 + (u2 - v2)^2 + ... + (un - vn)^2 ) */
  115. for (; i < VECTOR_SIZE; i++)
  116. sum += pow(u[i] - v[i], 2);
  117. return sqrt(sum);
  118. }
  119. bool trouver_solution_initiale(void)
  120. {
  121. size_t i;
  122. for (i = 0; i < N_VECTORS; i++)
  123. solution_opt[i] = rand() % n_clusters;
  124. return solution_valide(solution_opt);
  125. }
  126. bool solution_valide(const solution s)
  127. {
  128. /* This function returns true if the solution that it found is "valid",
  129. * i.e., it has at least one element in each cluster. */
  130. bool *cluster_empty = calloc(n_clusters, sizeof *cluster_empty);
  131. bool valid = true;
  132. int i;
  133. for (i = 0; i < n_clusters; i++)
  134. cluster_empty[i] = true;
  135. for (i = 0; (size_t) i < N_VECTORS; i++)
  136. cluster_empty[s[i]] = false;
  137. for (i = 0; valid && i < n_clusters; i++)
  138. valid = (valid && !cluster_empty[i]);
  139. free(cluster_empty);
  140. return valid;
  141. }
  142. void print_solution(const solution s, const char *name)
  143. {
  144. size_t i = 0;
  145. printf("%s: [\n", name ? name : "Solution");
  146. while (i < N_VECTORS) {
  147. const char *end;
  148. if (i + 1 == N_VECTORS)
  149. end = "]\n";
  150. else if ((i + 1) % 23 == 0)
  151. end = ",\n";
  152. else
  153. end = ", ";
  154. printf("%d%s", s[i++], end);
  155. }
  156. }
  157. void print_vector(const vector v, const char *name)
  158. {
  159. size_t i = 0;
  160. printf("%s: [\n", name ? name : "Vector");
  161. while (i < VECTOR_SIZE) {
  162. const char *end;
  163. if (i + 1 == VECTOR_SIZE)
  164. end = "]\n";
  165. else if ((i + 1) % 7 == 0)
  166. end = ",\n";
  167. else
  168. end = ", ";
  169. printf("%.5f%s", v[i++], end);
  170. }
  171. }
  172. vector *centres_gravite(const solution s)
  173. {
  174. /* Calculer le centre de gravité pour les vecteurs du cluster cluster selon la solution s */
  175. int cluster;
  176. size_t i = 0;
  177. /* cgs[n_clusters] est le centre de gravité global */
  178. vector *cgs = calloc(n_clusters + 1, sizeof(*cgs));
  179. int *vectors_in_cluster = calloc(n_clusters + 1, sizeof(*vectors_in_cluster));
  180. if (!cgs || !vectors_in_cluster)
  181. abort();
  182. for (cluster = 0; cluster < n_clusters + 1; cluster++) {
  183. if (!(cgs[cluster] = calloc(VECTOR_SIZE, sizeof(*cgs[cluster]))))
  184. abort();
  185. /* Initialiser à 0 */
  186. while (i < VECTOR_SIZE)
  187. cgs[cluster][i++] = 0;
  188. if (cluster < n_clusters)
  189. vectors_in_cluster[cluster] = 0;
  190. }
  191. for (i = 0; i < N_VECTORS; i++) {
  192. size_t j;
  193. cluster = s[i];
  194. ++vectors_in_cluster[cluster];
  195. for (j = 0; j < VECTOR_SIZE; j++) {
  196. cgs[cluster][j] += benchmark_data[i][j];
  197. cgs[n_clusters][j] += benchmark_data[i][j];
  198. }
  199. }
  200. vectors_in_cluster[n_clusters] = N_VECTORS;
  201. for (cluster = 0; cluster < n_clusters + 1; cluster++)
  202. for (i = 0; i < VECTOR_SIZE; i++)
  203. cgs[cluster][i] /= (double) vectors_in_cluster[cluster];
  204. free(vectors_in_cluster);
  205. return cgs;
  206. }
  207. int solution_voisine(solution *dest, const solution src)
  208. {
  209. /* This function changes about percentage% of the solution randomly */
  210. size_t i;
  211. const int cutoff = (int) ((long double) RAND_MAX / 100.0 * (long double) percentage);
  212. bool valid;
  213. if (!(*dest = calloc(N_VECTORS, sizeof(**dest))))
  214. abort();
  215. memcpy(*dest, src, N_VECTORS * sizeof(*src));
  216. assert(n_clusters > 1);
  217. for (i = 0; i < N_VECTORS; i++) {
  218. if (rand() < cutoff) {
  219. int new_cluster = rand() % (n_clusters - 1);
  220. /* To avoid the case where the cluster isn't actually changed. */
  221. new_cluster += (new_cluster >= src[i]);
  222. (*dest)[i] = new_cluster;
  223. }
  224. }
  225. if (!(valid = solution_valide(*dest))) {
  226. free(*dest);
  227. *dest = NULL;
  228. }
  229. return valid;
  230. }
  231. double fonction_objective(const solution s, double *inter, double *intra)
  232. {
  233. int i;
  234. double **cgs = centres_gravite(s);
  235. if (!cgs)
  236. abort();
  237. *inter = calculer_inter(cgs);
  238. *intra = calculer_intra(s, cgs);
  239. for (i = 0; i < n_clusters + 1; i++)
  240. free(cgs[i]);
  241. free(cgs);
  242. return *inter - *intra;
  243. }
  244. static double calculer_inter(const vector *cgs)
  245. {
  246. double inter = 0.0;
  247. int cluster;
  248. for (cluster = 0; cluster < n_clusters; cluster++)
  249. inter += distance(cgs[n_clusters], cgs[cluster]);
  250. return inter / (double) n_clusters;
  251. }
  252. static double calculer_intra(const solution s, const vector *cgs)
  253. {
  254. double intra = 0.0;
  255. int cluster;
  256. for (cluster = 0; cluster < n_clusters; cluster++) {
  257. double intra_for_this_cluster = 0.0;
  258. int vectors_in_this_cluster = 0;
  259. size_t i;
  260. for (i = 0; i < N_VECTORS; i++) {
  261. if (s[i] != cluster)
  262. continue;
  263. ++vectors_in_this_cluster;
  264. intra_for_this_cluster += distance(cgs[cluster], benchmark_data[i]);
  265. }
  266. intra += intra_for_this_cluster / (double) vectors_in_this_cluster;
  267. }
  268. return intra / (double) n_clusters;
  269. }