a saida não esta entregando o valores corretos

yasmimessi
(usa Outra)

Enviado em 01/12/2018 - 22:57h

olá, estou estudando o algoritmo firefley e peguei seu código na internet em linguagem c++, porem quando eu coloco para executar não acha a melhor função nem o melhor vaga-lume, acredito o erro esta na FunctionCallback. O codigo segue abaixo

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <time.h>

#include <string.h>

#include <memory.h>



#define DUMP	1

#define MAX_FFA	1000

#define MAX_D	1000



using namespace std;



int D = 1000;			// dimensão do problema

int n = 20;			// número de vagalumes

int MaxGeneration;		// número de interações

int NumEval;			// número de avaliações

int Index[MAX_FFA];		// tipo de vagalumes de acordo com valores de aptidão



double ffa[MAX_FFA][MAX_D];	// agentes vagalumes

double ffa_tmp[MAX_FFA][MAX_D]; // população intermediária

double f[MAX_FFA];		// valores de aptidão

double I[MAX_FFA];		// intensidade da luz

double nbest[MAX_FFA];          // a melhor solução até agora

double lb[MAX_D];		// limite inferior

double ub[MAX_D];		// limite superior



double alpha = 0.5;		// parâmetro alpha 

double betamin = 0.2;           // parâmetro beta 

double gama = 1.0;		// parâmetro gamma 

double fbest;			// a melhor função objetivo



typedef double (*FunctionCallback)(double sol[MAX_D]);



/*funções benchmark*/

double cost(double sol[MAX_D]);

double sphere(double sol[MAX_D]);



/*Escreva sua função objetivo*/

FunctionCallback function = &cost;



// opcionalmente recalcular o novo valor alfa

double alpha_new(double alpha, int NGen)

{

	double delta;			// delta parameter

	delta = 1.0-pow((pow(10.0, -4.0)/0.9), 1.0/(double) NGen);

	return (1-delta)*alpha;

}



// inicializar a população de vagalumes

void init_ffa()

{

	int i, j;

	double r;



	// inicializar os limites inferior e superior

	for (i=0;i<D;i++)

	{

		lb[i] = 0.0;

		ub[i] = 2.0;

	}



	for (i=0;i<n;i++)

	{

		for (j=0;j<D;j++)

		{

			r = (   (double)rand() / ((double)(RAND_MAX)+(double)(1)) );

			ffa[i][j]=r*(ub[i]-lb[i])+lb[i];

		}

		f[i] = 1.0;			// inicializar atratividade

		I[i] = f[i];

	}

}



// implementação de bubble sort

void sort_ffa()

{

	int i, j;



	// inicialização dos índices

	for(i=0;i<n;i++)

		Index[i] = i;



	// Bubble sort

	for(i=0;i<n-1;i++)

	{

		for(j=i+1;j<n;j++)

		{

			if(I[i] > I[j])

			{

				double z = I[i];	// troca de atração

				I[i] = I[j];

				I[j] = z;

				z = f[i];			// troca de aptidão

				f[i] = f[j];

				f[j] = z;

				int k = Index[i];	// troca de índices

				Index[i] = Index[j];

				Index[j] = k;

			}

		}

	}

}



// substituir a antiga população de acordo com os novos valores de índice

void replace_ffa()

{

	int i, j;



	// copiar população original para a área temporária

	for(i=0;i<n;i++)

	{

		for(j=0;j<D;j++)

		{

			ffa_tmp[i][j] = ffa[i][j];

		}

	}



	// seleção das gerações no sentido de EA

	for(i=0;i<n;i++)

	{

		for(j=0;j<D;j++)

		{

			ffa[i][j] = ffa_tmp[Index[i]][j];

		}

	}

}



void findlimits(int k)

{

	int i;



	for(i=0;i<D;i++)

	{

		if(ffa[k][i] < lb[i])

			ffa[k][i] = lb[i];

		if(ffa[k][i] > ub[i])

			ffa[k][i] = ub[i];

	}

}



void move_ffa()

{

	int i, j, k;

	double scale;

	double r, beta;



	for(i=0;i<n;i++)

	{

		scale = abs(ub[i]-lb[i]);

		for(j=0;j<n;j++)

		{

			r = 0.0;

			for(k=0;k<D;k++)

			{

				r += (ffa[i][k]-ffa[j][k])*(ffa[i][k]-ffa[j][k]);

			}

			r = sqrt(r);

			if(I[i] > I[j])	// mais brilhante e mais atraente

			{

				double beta0 = 1.0;

				beta = (beta0-betamin)*exp(-gama*pow(r, 2.0))+betamin;

				for(k=0;k<D;k++)

				{

					r = (   (double)rand() / ((double)(RAND_MAX)+(double)(1)) );

					double tmpf = alpha*(r-0.5)*scale;

					ffa[i][k] = ffa[i][k]*(1.0-beta)+ffa_tmp[j][k]*beta+tmpf;

				}

			}

		}

		findlimits(i);

	}

}



void dump_ffa(int gen)

{

	cout << "Dump at gen= " << gen << " best= " << fbest << endl;

}



/* mensagens de sintaxe no display */

void help()

{

	cout << "Syntax:" << endl;

	cout << "  Firefly [-h|-?] [-l] [-p] [-c] [-k] [-s] [-t]" << endl;

	cout << "    Parameters: -h|-? = command syntax" << endl;

	cout << "				 -n = number of fireflies" << endl;

	cout << "				 -d = problem dimension" << endl;

	cout << "				 -g = number of generations" << endl;

	cout << "				 -a = alpha parameter" << endl;

	cout << "				 -b = beta0 parameter" << endl;

	cout << "				 -c = gamma parameter" << endl;

}



int main(int argc, char* argv[])

{

        int i;

        int t = 1;		// contador de geração

         // manipulação de parâmetros interativos 

         for(int i=1;i<argc;i++)

         {

            if((strncmp(argv[i], "-h", 2) == 0) || (strncmp(argv[i], "-?", 2) == 0))

            {

    		help();

    		return 0;

            }

            else if(strncmp(argv[i], "-n", 2) == 0)         // número de vagalumes

            {

    		n = atoi(&argv[i][2]);

            }

            else if(strncmp(argv[i], "-d", 2) == 0)		// dimensão do problema

            {

    		D = atoi(&argv[i][2]);

            }

            else if(strncmp(argv[i], "-g", 2) == 0)		// número de gerações

            {

    		MaxGeneration = atoi(&argv[i][2]);

            }

            else if(strncmp(argv[i], "-a", 2) == 0)		// parâmetro alpha

            {

    		alpha = atof(&argv[i][2]);

            }

            else if(strncmp(argv[i], "-b", 2) == 0)		// parâmetro beta

            {

    		betamin = atof(&argv[i][2]);

            }

            else if(strncmp(argv[i], "-c", 2) == 0)		// parâmetro gamma

            {

    		gama = atof(&argv[i][2]);

            }

            else

            {

    		cerr << "Fatal error: invalid parameter: " << argv[i] << endl;

    		return -1;

            }

        }



        // laço de otimização do algoritmo firefly

        // determinar o ponto de partida de gerador aleatório

	srand(1);



	// gerar os locais iniciais de n vagalumes

	init_ffa();

#ifdef DUMP

	dump_ffa(t);

#endif



	while(t <= MaxGeneration)

	{

		// esta linha de reduzir alfa é opcional

		alpha = alpha_new(alpha, MaxGeneration);



		// avaliar novas soluções

		for(i=0;i<n;i++)

		{

                        f[i] = function(ffa[i]);                        // obtêm aptidão de solução

			I[i] = f[i];					// inicializar atratividade

		}



		// Classificação dos vagalumes pela sua intensidade de luz

		sort_ffa();

		// substituir população mais velha

		replace_ffa();



		// encontrar o atual melhor

		for(i=0;i<D;i++)

			nbest[i] = ffa[0][i];

		fbest = I[0];



		// mover todos os vagalumes para os melhores locais

		move_ffa();

#ifdef DUMP

		dump_ffa(t);

#endif

		t++;

	}



	cout << "End of optimization: fbest = " << fbest << endl;



	return 0;

}



// função teste FF 

double cost(double* sol)

{

	double sum = 0.0;



	for(int i=0;i<D;i++)

		sum += (sol[i]-1)*(sol[i]-1);



	return sum;

}



double sphere(double* sol) {

	int j;

	double top = 0;

	for (j = 0; j < D; j++) {

		top = top + sol[j] * sol[j];

	}

	return top;

}

 

paulo1205
(usa Ubuntu)

Enviado em 03/12/2018 - 11:09h

Prezado,

Eu não cheguei a compreender para que serve seu algoritmo, e portanto não sei dizer ao certo se ele está certo ou não.

Entretanto, seu código tem umas coisas meio diferentes do que se poderia esperar, especialmente quando você usa C++, em vez de C. Algumas delas até erradas.

Eis alguns pontos que eu acho que você poderia rever.

  • Paradigma de programação. Algoritmos para tratar problemas semelhantes e que usam funções de callback para distingui-los entre si são candidatos naturais a ser modelados como classe base, contendo código comum, e classes derivadas, que implementam especializações na forma de funções-membros (ou métodos) virtuais. Já que você está usando uma linguagem que o habilita a usar POO, você poderia modelar seu programa dessa maneira.

  • Cabeçalhos ao estilo do C num programa C++. Em vez de “<math.h>” ou “<stdlib.h>”, prefira “<cmath>” e “<cstdlib>”. (Não chega a ser um erro usar as versões do C, mas não é o que se espera num programa em C++, até porque as versões em C++ costumam agregar funcionalidades a funções do C, principalmente voltadas à segurança de tipos de dados e a programação genérica.)

  • Excesso de variáveis globais. Algumas delas só aparecem dentro de uma ou outra função específica, o que indica que pode fazer sentido movê-las para dentro de tais funções (ou para dentro da classe, se você decidir remodelar seu programa, de acordo com a primeira sugestão). (Também não é um erro em si, mas geralmente o uso de variáveis globais em excesso tende a criar mais dificuldades para manutenção de código, e é percebida como uma forma deselegante de programação.)

  • Arrays pré-dimensionados. Limitar o tamanho máximo do problema em função do uso de arrays tradicionais do C leva a duas consequências indesejáveis: desperdício de recursos, caso você decida executar um problema menor, e a necessidade de recompilar o programa quando você quiser computar um problema maior do que o previsto inicialmente. Aproveite que o C++ tem std::vector, que tem dimensionamento dinâmico de baixo-custo e de sintaxe conveniente, e use-o em lugar dos arrays estáticos.

  • Arrays com todos os valores iguais e constantes. Os arrays lb e ub têm todos os seus respectivos elementos iguais, e com valores que, depois de inicializados, não mudam ao longo da execução do programa. Então por que ter arrays, em vez de apenas escalares declarados como constantes?

  • Parâmetro ponteiro com aparência de array. Na declaração do tipo FunctionCallback e nos protótipos das funções sphere() e cost() você colocou parâmetros na forma de array (“double sol[MAX_D]”). Entretanto, devido à forma como C trata arrays, ponteiros e passagem da argumentos para funções (forma essa herdada pelo C++), esses aparentes arrays, quando declarados como parâmetros de funções, serão interpretados como meros ponteiros, e o valor da dimensão será totalmente desconsiderado. Você possivelmente até já sabe isso, pois na implementação dessas funções você usou a forma como ponteiro. Sendo assim, por que não uniformizar a declaração e a definição?

  • Chamada a funções para calcular valores constantes (e de fácil representação). Por que usar “pow(1.0, -4.0)” em lugar de simplesmente “1.0e-4”, ou “(double)1” em lugar de simplesmente “1.0”?

  • Possibilidade de trocar divisão por multiplicação. Divisões são quase sempre mais custosas do que multiplicações. Assim sendo, quando você tem uma divisão por um valor constante, pode ser interessante trocá-la uma uma multiplicação por um fator que seja o inverso do divisor. Assim, em vez de “rand()/((double)RAND_MAX+1.0” (dentro de um laço de repetição, ainda por cima), você poderia declarar uma unica vez uma constante para normalizar seus números aleatórios que fosse um fator, em vez de um divisor, como mostrado abaixo. (Pode ser que o compilador consiga otimizar essa operação, fazendo implicitamente o mesmo que o exemplo a seguir. Contudo, para isso você precisará, no mínimo, de ligar as opções de otimização de código. Costuma fazê-lo?)

const double RAND_NORMALIZE_FACTOR=1.0/(RAND_MAX+1.0);



/* ... */



void init_ffa(){

  /* ... */

        r=rand()*RAND_NORMALIZE_FACTOR;

  /* ... */

} 

  • Uso de rand()/srand(). As versões tradicionais de rand()/srand() têm, em muitas implementações, baixa aleatoriedade. E como você manda o programa sempre inicializar o PRNG com o mesmo valor de semente (ao fazer sempre “srand(1)”, em lugar de usar uma semente variável, com algo como srand(time(nullptr)+getpid())), aí mesmo é que suas simulações tendem a ficar mais pobres. Considere usar as funções de PRNG da biblioteca do C++, que foram projetadas para ser melhores do que as tradicionais do C, ou pelo menos mude a forma de inicializar a semente com srand().

  • Ordenação com Bubble Sort. Algoritmo lento. Com mil elementos (que é o tamanho que você prealoca para seus arrays), a complexidade da sua ordenação pode ir para a ordem de milhão de operações. Considere usar um algoritmo de ordenação mais eficiente, como o Merge Sort. Para tanto, porém, talvez seja melhor ver também os próximos dois itens.

  • O array Index. Parece-me que a função dele é servir como uma forma de reordenar as linhas das matrizes ffa e ffa_tmp, sem ter de fazer a troca de cada elementos dessas linhas. Se for esse o caso, eis uma outra vantagem de usar std::vector (no caso de matrizes, numa forma parecida com “std::vector<std::vector<double>> ffa”, por exemplo): você poderia fazer a troca das linhas ffa[i] e ffa[j] com um simples “std::swap(ffa[i], ffa[j])” e com custo baixíssimo, menor do que colocar uma dupla indireção mais tarde a cada acesso (na função replace_ffa()).

  • Acoplamento (ou sua falta) entre dados correlatos. Aparentemente os arrays I, f e ffa (e possivelmente ffa_tmp e nbtest, mas não consegui analisá-los com o devido cuidado) andam juntos, inclusive na hora em que a ordenação rearruma seus elementos. Sendo assim, será que eles não poderiam ser postos como campos de uma estrutura, tendo I (possivelmente renomeado para algo mais descritivo, tal como intensity ou brightness) como chave de ordenação? Algo como o seguinte.

struct ffa_info {

  double brightness, fitness;

  vector<double> agents;



  ffa_info(size_t dimension, double lb=1.0, double ub=2.0):

    brightness(1.0), fitness(1.0)

  {

    agents.reserve(dimension);

    while(dimension--)

      agents.push_back((ub-lb)*rand()*RAND_NORMALIZE_FACTOR-lb);

  }



  // Função para permitir o uso de std::sort.

  bool operator<(const ffa_info &other){ return brightness<other.brightness; }

};



class ffa_base {

  private:

    vector<ffa_info> fireflies;



  public:

    ffa_base(size_t n_fireflies, size_t dimension):

      ffa(n_fireflies, ffa_info(dimension))

    {

    }



    virtual double objective(const vector<double> &agents) = 0;  // Função virtual pura, a ser implementada nas classes derivadas.



    void next_generation(){

      for(auto &firefly: fireflies)

        firefly.brightness=firefly.fitness=objective(firefly.agents);

      sort(fireflies.begin(), fireflies.end());

    }



    double fbest(){ return fireflies[0].brightness; }

    void move(){ /* ... */ }

    void dump(ostream &os){ /* ... */ }

    /* ... o que mais for necessário ...*/

};



class ffa_cost: public ffa_base {

  public:

    using ffa_base::ffa_base;  // Herda construtores da classe base.



    double objective(const vector<double> &agents){

      double sum=0.0;

      for(auto ag: agents)

        sum+=(ag-1)*(ag-1);

      return sum;

    }

};



class ffa_sphere: public ffa_base { /* ... */ }; 

yasmimessi
(usa Outra)

Enviado em 03/12/2018 - 19:54h

obrigado pela analise e ajuda! vou da uma olha nas partes que o senhor mencionou e vou tentar ajeitar. Obrigada!