Skip to content
kkw
조회 수 236 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

정렬공부를 하다가 우연히 보고정렬에 대해 알게되었다

이 보고정렬이란것이 골 때리는것이 수가 정렬될때까지 무작위로 수의 위치를 옮기는것이다. 

무려 평균 시간복잡도 O(n * n!), 최악의 경우  O(∞) 라는 엄청난 효율을 보여준다!

 

이런 비효율적인 보고정렬에 유전알고리즘을 넣으면 꽤나 쓸만하다구 꺼무위키  에서 말해서

c언어로 보고+유전알고리즘을 짜보았다. 

 

유전알고리즘은 선택 교차 변이 대치 연산을 반복하면서 최적의 해를 찾는것인데 어떤 연산을 선택하느냐 혹은 유전자의 개수, 돌연변이 확률에 따라서 성능의 차이가 크다.

 

룰렛휠에 대한 이미지 검색결과 <- 룰렛휠 

 

선택연산에서는 품질비례룰렛휠 선택이 가장 적합한 알고리즘이지만 구현하는데 힘들어서 토너먼트 선택을 이용하여서 선택연산을 진행하였다.

 

일점교차에 대한 이미지 검색결과

교차연산에서는 

다점 교차가 유전자의 다양성을 주지만 귀찮아서 일점교차를 무작위로 주었다. 

 

변이 연산에서는 

OMG를 통해서 일정 1/OMG 확률로 돌연변이가 나오게하였다. 

 

적합도의 판정은 

각각의 숫자가 올바른 위치에 있다면 적합도에 +1 점을 주었다. 

제목 없음.png

ex) 2와 4가 올바른 위치에 있기에 적합도는 2가 된다

 

<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
 
#define Cdata 10 //정렬할 데이터 갯수 지정//
#define MMGEN 1000 // 세대별 유전자 갯수 조절 //
#define CGEN  500 //선택될 유전자 갯수 조절//
#define OMG   1 //돌연변이 확률//
 
void rnd(void);
void otp();
int MGEN = 0stack = 0, Sc = 0, CC = 0;
 
 
int number[Cdata] = { 1,5,2,3,4,6,7,8,9,10 }; //정렬해야할 데이터//
 
 
typedef struct //구조체로 유전자 저장 공간 마련//
{
    int Gene[Cdata + 1]; //적합도+유전체 저장//
    int TGene[Cdata + 1]; // 임시 저장 공간//
    int ChGene[Cdata + 1]; //자식 유전자 저장공간//
 
}GeneData;
 
GeneData S_save[MMGEN];
GeneData C_save[CGEN / 2];
 
void Switchg() // 자식 유전자 생성//
{
    int temp;
    for (int k = 0; k < CGEN / 2; k++)
    {
        for (int i = 1; i <= Cdata / 2; i++)
        {
            C_save[k].ChGene[i] = S_save[k].Gene[i];
        }
        for (int i = 4; i <= Cdata; i++)
        {
            C_save[k].ChGene[i] = S_save[k + 1].Gene[i];
        }
 
    }
 
    for (int i = 0; i < CGEN / 2; i++)   //자식 유전자 데이터를 반영//
    {
        for (int j = 0; j <= Cdata; j++)
        {
            S_save[i + CGEN].Gene[j] = C_save[i].ChGene[j];
        }
    }
 
    if (1 == rand() % OMG + 1//돌연변이//    
    {
        S_save[(CGEN / 2+ CGEN + 1].Gene[rand() % Cdata + 1= number[rand() % Cdata];
 
    }
 
    printf("-생성된 자식 유전자-\n");
 
    for (int i = 0; i < CGEN / 2; i++)
    {
        for (int j = 0; j <= Cdata; j++)
        {
            printf("%d", C_save[i].ChGene[j]);
        }
        printf("\n");
    }
    CC++;
 
    printf("\n");
 
    if (Discrim() == 1)
    {
        printf("반복횟수:%d", CC);
        printf("축하합니다 정렬되었습니다");
 
    }
 
}
 
void Selection()  //선택 함수//
 
{
    int k = 0;
 
    for (int i = 0; i < MMGEN; i++)   //정렬을 하기위해 정렬하는 흑우가 있따?~!!)//
    {
        for (int j = i + 1; j < MMGEN; j++)
        {
            if (S_save[i].Gene[0<= S_save[j].Gene[0])
            {
                for (int k = 0; k < Cdata + 1; k++)
                {
                    S_save[i].TGene[k] = S_save[i].Gene[k];
                }
                for (int k = 0; k < Cdata + 1; k++)
                {
                    S_save[i].Gene[k] = S_save[j].Gene[k];
                }
                for (int k = 0; k < Cdata + 1; k++)
                {
                    S_save[j].Gene[k] = S_save[i].TGene[k];
                }
 
            }
 
        }
 
    }
    printf("-선택된 부모 유전자-\n");
    for (int k = 0; k < CGEN; k++)
    {
        for (int i = 0; i < Cdata + 1; i++)
        {
            printf("%d", S_save[k].Gene[i]);
        }
        printf("\n");
    }
    
    Switchg();
}
 
 
 
void otp() //출력함수 //
{
 
    for (int i = 0; i < MMGEN; i++)
    {
        for (int j = 0; j <= Cdata; j++)
        {
            printf("%d", S_save[i].Gene[j]);
        }
        printf("\n");
    }
 
 
}
 
int Discrim(void//보고보고 정렬 적합도 평가 함수, 보고보고 정렬함수//
{
    int k = 0;
    for (int j = 0; j < MMGEN; j++)
    {
        k = 0;
        for (int i = 1; i <= Cdata; i++)
        {
            if (S_save[j].Gene[i] == i)
            {
                k++;
            }
        }
        S_save[j].Gene[0= k;
 
        if (k == Cdata)
        {
            return 1;
        }
    }
 
 
    otp(); //화면에 적합도와 유전자 출력//
    Selection();
}
 
void save() //저장함수//
{
 
    for (int i = 0; i < Cdata + 1; i++//유전자 저장
    {
        S_save[Sc].Gene[i + 1= number[i];
    }
    Sc++;
 
    if (Sc == MMGEN) //저장을 다하고 나서 선택//
    {
        Discrim();
    }
    rnd();
}
 
void rnd(void// 보고보고 정렬 랜덤 함수//
{
 
    int random;
    int temp; //스왑을 위한 임시변수//
 
    for (int i = 0; i < Cdata; i++)
    {
        random = rand() % Cdata;         // 랜덤값초기화// 
        temp = number[i];
        number[i] = number[random];
        number[random] = temp;
    }
 
    MGEN++;
 
    if (MGEN <= MMGEN)
    {
        save();
    }
 
 
}
 
int main(void)
{
    int hope;
    srand(time(NULL));
 
    rnd();
 
 
    return 0;
}
 
 
cs

 

사실 이 프로젝트는 1년전에 짠코드인데 함수안에 함수를 불러오게되면서 계속 실행하게되면 스택오버플로우가 발생한다.

또한 보고정렬보다 나으나 당시 나의 한계? 때문에 적합한 연산을 하지 못해 유전자의 다양성이 부족해졌다

시간이 있으면 선택연산과 교차연산의 방식을 바꿔 유전자의 다양성을 유지할수 있으면 좋겠다.

 

 

 

?

List of Articles
번호 제목 글쓴이 날짜 조회 수
» 보고정렬+유전알고리즘 file kkw 2019.07.30 236
Board Pagination Prev 1 Next
/ 1

Powered by Xpress Engine / Designed by Sketchbook

sketchbook5, 스케치북5

sketchbook5, 스케치북5

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

설치 취소