West_Cold

확률과정
-time step: 이벤트 발생 시점
-간격:시간 간격이 일정(현실은 다르지만)
-수:이벤트 수가 유한함(무한할 수 있는 경우도 존재)
-T:발생하는 이벤트의 총 숫자

State
-존재 가능한 모든 state의 집합
-개수가 유한하다고 가정

Action
-존재 가능한 모든 Action의 집합
-Discrete Action space:action유한하고 그중 한개를 택
-Continuous Action space:action이 무한하고 n차원 백터로 표현됨

Reward
-r t+1:st에서 at를 수행하였을 때의 가치


Transition Probability(전이 확률)
-P(궁금l조건)->확실하지 않아 확률 도입
-MDP시점에서는 다음 상태의 값은 직전 상태에서만 액션을 받고 그 이전 히스토리는 관계가 없다
-MDP가 강화학습에 성능이 좋음


감가상각
-reward는 항상 고유한가?
-적용: (rt)*(r의 T-t-1승)

Markov Decision Process(MDP)
-5개 듀플로 정의:M=(S,A,R,r,P)
-S:State
-A:Action
-R:Reward
-P:Transition probability
-r:감가상각


MDP의 목적
-reward합을 최대화 하고 싶음
-그러려면 action을 적절하게 잘 선택해야 함
-잘 선택하려면 현재 상황에 맞는 액션을 선택
-적절한 액션 선택이란 현재 상태에서 기워드 합을 최대화 하는 액션을 선택
-당장 근시안적으로 reward가 아닌 합을 최대화

Value Function
-state-value function: state의 가치 함수
state value를 최대화 하면서 행동을 수행해 나가고 싶음

-**Action-value function:state-action 쌍의 가치함수
-st에서 at를 수행한 뒤,지 속적으로 action을 수행해 sT에 도달했을때,discount facor를 고려한 미래 reward 총합
Q-value라 부른다:optimal action-value function(최적의 reward총합)

Value function 구하는 방법
Dynamic Programming(DP)-동적계획법
-최적화 분야 방법론 중 하나
-데이터가 많을 수록 계산량이 폭발하여 현실적으로 사용하기 힘듬
Reinforcement Learning(RL)-강화학습
-최적해를 근사하도록 가치 함수를 학습
-머신러닝 3분류 중 하나

강화학습이란
-연속적 의사결정 문제를 풀기 위한 머신러닝 기법
-(State, Action, Reward, Next state)->training data
-요소:Time(이산적), st, at, rt+1

transition(st, at, st+1, at+1...)
episode:싸이클(s1,a1,r2,s2)/a2....
-agent의 목표: 매st마다 미래 리워드 총합을 최대화 하는 at수행
-RL의 목표:agent의 목표를 만족하도록 학습시킴
-강화학습의 철학->Approximation(근사)
-Exploration
-Exploitaion

왜 지도학습보단 강화학습일까?
-현실에선 고급 데이터 구하기 힘드니 환경만 세팅해줘서 학습시킴
-연속적 의사결정 문제의 속성을 가진 문제를 해결하고자 할때
-환경 구축하여 데이터를 생성할 수 있을 때

선택연산

-교차에 쓰이는 두 개의 부모해를 고르기 위한 연산
-선택압을 이용하여 해의 선택 확률을 조절 할 수 있음
*선택압:우수한 해들과 열등한 해들 사이의 적합도 차이(높을 수록 exploit/낮을 수록 explore)
*적합도: 풀고자 하는 문제에 주어진 해가 적합한 정도->평가

품질 비례 룰렛휠 선택
-각 해의 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 k배가 되도록 조절함
-해집단 내의 i번째 해의 적합도 fi는 다음과 같이 계산됨
fi=(Cw-Ci)+(Cw-Cb)/(k-1),k>1
Cw:해집단 내에서 가장 나쁜 해의 비용
Cb:해집단 내에서 가장 좋은 해의 비용
Ci:해의 i의 비용
k를 높이면 선택압이 높아짐->우수한 해가 선택될 확률과 열등한 해가 선택될 확률의 차이가 커짐

-각 염색체는 룰렛휠 상에 자신의 적합도 만큼의 공간을 배정 받음
-대부분의 경우 해집단에서 가장 좋은 해와 나쁜 해의 품질의 차이가 굉장히 크기 때문에, k를 사용하지 않고 해의 품질을 그대로 적합도로 사용하면 나쁜 해들의 선택 기회가 박탈됨->엄청나게 큰 선택압을 주어 해의 다양성을 급속히 떨어트리는 결과를 초래함


토너먼트 선택
-편해서 가장 많이 사용
-두개의 염색체를 임의로 선택하여 0과 1 사이의 난수를 발생시켜서, 이 값이 t보다 작으면 두 염색체 중 품질이 좋은 것을 선택하고 그렇지 않으면 품질이 나쁜 것을 선택
-t는 파라미터화 할 수 있는 값으로, t 값이 높을 수록 선택압이 높아짐
-t가 0.5 근처이거나 이보다 작은 것은 비합리적임
-일반적으로는 2의k승개의 염색체를 선택한 다음 이들을 토너먼트 형식으로 걸러내어 마지막으로 남은 것을 선택하는 방법도 존재(k가 크면 선택압이 높아짐)

순위 기반 선택
-간격은 같게 해주겠다
-품질 비례 선택에서는 k값을 조정함으로써 좋은 품질과 나쁜 품질의 해들의 적합도 차이의 지나친 증가를 막을 수 있음/다만 해들의 적합도 분포는 조절할 수 없음
-순위 기반 선택은 해집단 내의 해들을 품질 순으로 '순위'를 매긴 다음 가장 좋은 해부터 일차 함수적으로 적합도를 배정함
-n개의 염색체 중 i번째 순위를 가진 염색체의 적합도는 다음과 같이 계산됨/
fi-max+(i-1)*(min-max)/(n-1)/이 식에서 max와 min의 값 차이를 바꿈으로써 선택압을 조절할 수 있음
-해들의 적합도는 max와 min 사이에서 균일한 간격으로 분포하게 됨

교차연산

-유전 알고리즘의 대표적인 연산이며, 연산 중 가장 다양한 대안이 존재함
-선택연산을 통해 선택된 두개의 해를 부분 결합하여 새로운 해를 만들어냄
-해의 표현은 교차 연산과 관계되어 있을 때만 의미가 있음
  -A라는 방법으로 해를 표현했는데 교차 연산에서 이름 바꾸어 사용한다면 염색체가 A라는 방법으로 표현되었다고 할 수 없음
-가장 대표적인 일점교차 가 있음(자르는 방법은 n-1개)

산술적 교차 연산
-거의 사용하지 않는다
-실수 염색체를 사용하는 경우에 사용할 수 있는 교차 연산
-염색체의 각 위치에 대해 두 부모 염색체의 두 유전자 값의 평균을 구해 자식해의 해당 위치로 배정함
-산술적 교차는 수의 '크기'라는 개념을 교차 연산에 사용한다는 점에서 매력있는 연산임
-하지만, 산술 평균을 지향하므로 매우 빠른 수렴을 보이는 경향이 있음->변이 등을 적절히 조절하여 설익은 수렴에 이르지 않도록 유의해야 함

TSP와 GA
chromosome 표현(1)
-위치 기반 표현: 유전자의 위치가 해당 유전자의 속성을 결정함
-순서 기반 표현: 인접한 유전자의 값들이 무엇인지 중요함

chromosome 표현(2)
-순서 기반 표현:이해하기 쉽고 밀접한 관계를 갖는 도시들이 염색체에 가까운 위치에 자리하여 교차 연산시 중요한 스키마의 생존 확률 증가
-위치 기반표현: 하나의 해는 단 하나의 염색체에 대응됨/위치i는 다음도시j의 다음 방문도시를 나타냄


싸이클 교차-TSP와 같이 염색체가 순열로 표현되는 경우 적용 가능한 교차 연산
-중복x/빠뜨리기x
-그림보기

순서교차
-싸이클 교차와 마찬가지로 염색체 순열로 표시되는 경우 사용될 수 있는 교차연산
-그림

PMX
-그림

변이연산

-부모해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산
-교차 연산이 만들어 놓은 자식해를 미소하게 변형하여 새로운 해를 만들어 내는 연산
-전형적인 변이 연산은 각각의 유전자에 대해[0,1) 범위의 난수를 생성하여 미리 정한 임의의 임계값 미만의 수가 나오면 해당 유전자를 임의로 변형시키고 그 이상의 수가 나오면 변형하지 않음
-전형적인 임계값으로 0.015, .0.01등이 있는데, 문제의 성격과 유전 알고리즘의 다른 연산들의 종류에 따라 변할 수 있음
-변이 연산은 임의로 일어나므로 변이는 절대적인 비율로 해의 품질을 저하시킴
-변이로 잘못만들어진 유전자는 시간이 흐르면서 사라지고 가끔 발생하는 성공적인 변이는 해집단의 품질을 향상시키는데 기여함
-변이의 확률을 높이면 다양한 해를 생성할 수 있으므로 유전 알고리즘의 역동성은 늘어나지만 해집단의 수렴성이 떨어져 알고리즘의 수행시간이 길어지고 개선 속도가 느려짐


전통적인 변이
-염색체를 2진수 형태로 바꾸어 변이를 수행
-변이 연산을 수행할 때는 염색체의 구조가 문제의 정의 혹은 제약을 위반하지 않는지 고려해야 함

cut mutataion
-염색체가 순열로 표시되는 경우 사용될 수 있는 변이 연산


inverse mutation
exchange mutation
scramble mutation(임의)

대치연산

-교차와 변이 연산으로 새로운 해를 반든 후에 이를 해집단 내의 어떤 해와 대치할지 결정하는 연산
-한 세대에서 만들어지는 해의 개수 k는 해집단에서 대치되는 해의 개수이기도 함-세대차:k/n

세대형 유전 알고리즘
-대다수 물갈이라 대치 연산에 큰 고민을 할 필요가 없음

안정 상태 유전 알고리즘
-세대차가 1/n에 가까운 유전 알고리즘, 새로운 해가 생기자마자 해집단에 넣어주는방식
-해집단을 빨리 수렴시키는 경향이 있는 대신 설익은 수렴의 가능성도 큼
-한 개 또는 소수의 해가 생기는 즉시 해집단 내의 해와 대치되므로 대치될 대상을 고르는 것이 매우 중요함
방법(1)엘리티즘
방법(2)두 부모 해 중 품질이 나쁜 해와 대치하는 방법
방법(3)해집단 전체를 비교하여 자신과 가장 가까운 해를 대치하는 방법

뻐꾸기 번식

-Levy flight
해당 지점 주위에서 맴돌다가 일정 시간 이후에 멀리 떨어진 지점을 이동하는패턴이 반복됨
exploitation:짧은 이동
exploration:긴 이동

pso

-물고기나 새들이 군집을 지어 이동하는 패턴에서 착안된 메타유리스틱 알고리즘
-최초로 연구되었을 때는 사회적인 행동을 시뮬레이션 하기 위해 개발되었음
-유전알고리즘과 다르게 해의 표현이 연속적인 형태일때 적합함
-식-그림

-pso는 자신 교차가 없으니 대체가 없다

w:입자의 속도에 대한 가중치
c1:자신의 최고 위치에 대한 가중치
c2:집단의 최고 위치에 대한 가중치
r1,r2:0과1 사이의 난수
위치 업데이트 식:그림



w이 증가하면->움직임 활발함
c1이 감소하면 exploration이 감소->입자들이 수렴함
c2가 증가하면 exploitaion->개인 행동에 치중

NP-hard Problem

TSP
-하나의 도시에서부터 시작해서 모든 도시를 한 번씩만 방문하여 다시 시작점을 돌아오는 최단 거리를 구하기
-열거말고는 방법이 존재하지 않음(ex 70개 도시(70-1)!/2)
-고유한 구조 때문에 효율적인 알고리즘이 존재하지 않음
-이런 문제들 중 한 문제라도 효율적을 풀 수 있으면, 다른 모든 문제들도 풀 수 있음
-이런 문제들을 NP-hard문제라고 한다


serach algorithm
-Brute Force seach:어떤 주어진 문제를 해결하기 위해 정해진 규칙을 위반하지 않는 모든 규칙을 나열
-dynamic programming

np-hard problem
-어떤 문제가 주어지면 그 문제가 np-hard문제인지 판단이 필요
-맞다면 정확한 최적해를 구하는 알고리즘을 추구하는 것은 시간 낭비
-그렇다면 해를 얻는것은 불가능?->no->근사해
-데이터가 특별한 구조를 가지고 있어서 해법이 존재할 수도 있음
-최적해는 아니지만 근사해를 효율적으로 구하는 방법이 존재함


knapsack problem
-여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제->수리적 모형

T최소화
-spt/edd/slack 다 안되는 경우도 있다

->너무 어렵다 보니 메타휴리스틱 알고리즘이 나왔다
metaheuristic

정의
▪ 컴퓨터 과학 및 수학적 최적화에서 메타휴리스틱은 다음을 수행하도록 설계된 상위 수준 절차 또는 휴리스틱
문제에 대해 "충분"히 좋은 솔루션을 제공할 수 있는 "경험적 방법"(부분 검색 알고리즘)을 찾고 생성하거나 선택합니다.
특히 불완전하거나 "불완전한 정보" 또는 "제한된 계산 용량"으로 인해 최적화 문제가 발생합니다.
메타휴리스틱스는 너무 커서 완전히 샘플링할 수 없는 솔루션 세트를 샘플링합니다.

속성
▪ 최적화 알고리즘과 비교하여 메타휴리스틱은 전역적으로 최적의 솔루션을 보장하지 "않는다."
▪ 메타휴리스틱으로 찾은 솔루션은 생성된 "무작위 변수 세트에 따라 달라진다."
▪ 조합 최적화에서는 실현 가능한 솔루션의 큰 집합을 검색함으로써 메타휴리스틱이 종종 좋은 점을 찾을 수 있다.
최적화 알고리즘, 반복 방법 또는 간단한 경험적 방법보다 "계산 노력이 덜 드는 솔루션"




메타휴리스틱 예시들
-Genetic algorithm(popolation, evolutionary algorithm, naturally inspired)
-Tabu seach(trajectory, short time memory)
-cuckoo seach(popolation, evolutinonary algorithm, naturally inspired, levy flights)


진화 알고리즘
-생물의 진화과정을 문제 해결 과정에 적용한 알고리즘
-세대를 거듭할 수록 우수한 성능의 해는 살아남고, 열등한 성능의 해는 도태됨(하나의 해가 하나의 개체에 대응됨)
-해공간이 넓고 복잡한 문제에서 우수한 해를 탐색하기 위해 사용됨


GA
-근간이 되는 알고리즘
-집단 유전학의 개체 진화 원리를 이용하여 해 공간을 탐색하는 방법
-집단 유전학의 개체 진화 원리를 이용하는 solution sapce search 방법
-key features
적자생존/교차연산/돌연변이/집단(population)/대체/평가
-염색체:임의의 해를 GA가 이해할 수 있는 형태로 표현한 것/해/solution
-population(해집단):정해진 수로 운영되는 염색채들의 집단
-gene(유전자):염색체의 각 인자
-generation:GA의 하나의 루프


구조
(1)initalization
-n개의 초기 염색체 집단 랜덤으로 생성
-문제에 맞게 알고리즘들 이용
(2)evaluation and selection
-평가하고 부모 고르기
-각 해의 성능을 평가
-정의한 문제의 목적함수에 따른 성능을 계산
(3)crossover
-유전자 수는 같지만 적당한 부분만 교차로 받을 수 있다
-exploitation
-두해의 특징을 부분 결합하여 하나의 새로운 해를 만드는 연산
-두 부모해의 동일한 위치에 자름선을 정한 후, 각 부모해로부터 한 부분씩 가져와 합치면 새로운 해가 생성됨
(4)mutation
-랜덤으로 부모에게 없는 유전자를 수정해봄
-exploration
-해를 임의로 변형시키는 연산
-교차와 달리 부모해에 없는 속성을 도입하여 해의 다양성을 높이는 역할
-대부분 해의 품질이 낮아지는 결과로 이어짐
(5)replacement
-못하는 애들은 없애고 잘하는 대들을 복제
-해집단의 일부가 새로운 해로 대체됨(도태와 생존을 위해)
-교차와 돌연변이와 연관되어서 결정해야 함
-해를 대체하지 않고 특정 비율만큼만 생존시키는 방식도 존재


염색체 표현
-모든 해는 염색체로 표현되어야 함
-전형적인 유전 알고리즘은 해를 이진 스트링 모양의 염색체로 표현함(01010001)
-정수를 해로 삼을 때 이진수로 나타내면 자연스럽게 이진수로 표현 가능

스키마
-패턴
-임의의 염색체는 많은 부분적 패턴을 포함하고 있음
-1101은 16개의 패턴이 포함됨 1***/****/1*01
-유전 알고리즘은 작은 스키마들이 결합하여 점점 더 큰 스키마를 이루어가는 과정
초기 단계는 해의 품질은 좋지 않음
-그러나 이런 염색체들 속에 나중에 좋은 염색체를 구성할 부분 패턴(스키마)가 숨어있음
-작은 스키마에는 존재하지 않는 특성이 큰 스키마에서 창발하는 것이 유전 알고리즘의 중요한 특징

스케줄:어떤 것이 언제 일어나기로 되어 있는 지 알려줌
스케줄링: 스케쥴을 생성하는 프로세스/가지고 있는 자원을 어떤 과업을 수행하기 위해 시간에 따라서 활당하자 /일상에서 자원이 한정되어 있기에 스케쥴링은 필수적

제조업에서 스케쥴링이란
-자원: 기계
-업무: job이란 opreations으로 구성->ex.10개의 오퍼를 끝내야 하나의 잡이 끝난다
-shop: 일정을 계획하는 환경/생산라인


scheduling
-제조업에서 생산 실행하기 전 마지막 단계
-생산하기 전 마지막 단계
-여러개의 기계를 순서에 맞게 동시에 진행
-시간에 따라 여러기계
-셋업 체인지
-시간 개념o
-시간의 흐름에 따라 여러 기계를 어떻게 할당할지

sequencing
-오직 하나의 기계에 job 주문
-우선순위 job
-순서만 정한다(시간개념x)

제조 시스템의 운영단계

목표 계획 시스템
factory planning
factory planner

실행계획 시스탬
scheduling
scheduler

(생산 시작)
dispatching
dispatcher


간트차트
-x=시간/y=기계
-시간의 흐름에 따른 각 기계의 job들에 대한 작업 순서와 시간을 파악 가능
-복잡한 job 묘사 혹은 job들간의 상호 유기적 관계를 나타내느데 한계가 존재
-시각화에 기능이 중요한거지 너무 믿으면 안된다(로우 데이터를 확인하던가 해야한다)
-특정 lot의 흐름만 관찰 가능
-하얀색 공백-설비가 노는 시간
-빗금-intentional delay-나중을 위해 잠깐 기다렸다가 하는 시간

liveGantt:거대한 생산시스템

스케줄링의 기본적으로 알아야 하는 내용

input
-스케줄링 전 알고 있는 정보이며 소문자로 표현
-pj(processing timer): job j에게 요구 되는 실행 양
-rj(release date):작업 시작 가능 시간
-dj(due date):만기일(넘어가면 지각)
*single machine sequencing에서,
c3에 의해 pj는 processing time과 setup time도 포함
c1에 의해 rj는 arrival time과 유사한 의미,rj=0

output
-스케줄링 의사결정의 결과로 생성되는 정보이며, 대문자로 표현
-Cj(completion time):processing time이 끝난 시간
-Fj(flowtime):시스템에 job이 머문 시간=Fj=Cj-rj(single machine=Cj-0->Fj=Cj)
-Lj(lateness):초과한 시간=Lj=Cj-dj/음수면 작업을 빨리 끝낸것이고 양수면 작업을 늦게 끝낸것
-Tj(tardiness):지각=max{0,Lj}->음수면 0 양수면 Lj

모든 job에 대한 종합적인 성능 지표(중요도에 따라 사용된다)
-F=Fj의 합
-T=Tj의 합
-Fmax
-Tmax
-U=Tj의 갯수
-Cmax->단축시키는게 스케줄링에서 중요


Single Machine Sequencing(시간개념x)
*single machine problem의 조건
-c1:싱글 오퍼레이션은 job은 프로세싱 동시에 가능/어떤잡도 문제를 풀기 시작하는 순간에 다 바로 활당 가능->rj=0
-c2:기계는 한번에 하나의 job만 가능하다
-c3:setup times는 Pj에 포함되어 있다
-c4:job 표현은 미리 결정되어 알려져 있어야 한다/원래는 릴리즈 타임 같은게 확률에 따라 바뀐다(멀티)
-c5:기계는 계속적으로 가능하다(고장이 일어나지 않고)
-c6:기계는 쉴수없다(일이 계속 있으면)-intension delay 고려하지 않는다
-c7:작업이 시작 되면 방해없이 계속 진행된다-한번 일 시작하면 끝까지

n개의 job의 sequence는 각 job의 index들의 permutation과 대응됨
싱글머신의 해결의 숫자n!
premutation schedule-정수들의 나열(7가지 조건이 성립되어야 가능)
대괄호가 sequence안의 위치를 나타내는데 사용될 수 있음
[5]=2는 sequence의 5번째 job은 job 2
d[1]:sequence의 첫 번째 job의 납기

single machine problem의 의의
-매우 간단하며 다양한 shop들 중 특별한 case(모든 job이 하나의 오퍼로 구성)
-설비가 여러 대 있지도 않으며 연속된 단계도 존재하지 않음
-그러나 single machine problem의 분석 결과는 복잡한 shop의 문제에 적용될 heuristc의 기초가 될 수 있음
-복잡한 스케쥴링 문제는 간단한 single machine problem으로 분해될 수 있음

heuritic이란
-최적이 보장되진 않지만 실용적인 방법으로 완벽하진 않지만 충분히 즉각적인(빠른) 목표에 도달 할 수있다
-다양한 분야에 사용(법,ai)
-스케쥴링에서 dispatching rule도 일종

dispatching rule
-간단하게 구현 가능하며, 빠른 시간 내에 만족할 만한 수준의 solution을 얻을 수 있음
-제한적으로 사용이 가능하며, 특정 경우에는 매우 안 좋은 품질의 solution을 산출함
-FIFO:first in first out/min r
-SPT:shortest p
-LPT:longest p
-EDD:earliest d
-MST:min (slack time(dj-pj-t))
-CR:min (dj-t)/pj/ 남은시간/남은 일 / CR>1 여유/ =  t=dj/ <1 늦음
-MOR:남은 공정의 수가 많은 job부터 할당
-LOR:남은 공정의 수가 적은 job부터
-SSU:setup time이 짧은 job부터 할당
-SPTSSU: setup+processing time이 짧은 job부터 할당

rj가 없어야 single machine sequencing



납기가 없는 문제들
flowtime
-제품이 고객에게 도달하기까지의 시간(TAT)
-시간을 최소화하면 비용을 최소화 할 수 있음

inventory
-shop에 물리적으로 투자된 비용(저장공간의 확보)
-시스템에 존재하는 평균 job의 수를 최소화하면 inventory레벨을 낮게 유지할 수 있음

두 문제의 관계
-job의 순서는 F를 최소화 하면서 동시에 J를 최소화한다
-j(t):t시점에 잡의 갯수
-J:j(t)의 평균
-F:F[]의 합
-F[1]=p[1]
-F[2]=p[1]+p[2]
-A=F=J x Fmax
J와 F는 비례
-F는 달라질 수 있지만 Fmax는 상수
-F(t)의 면적은 경사가 점점 완만해질수록 최소화 됨
-짧은거 먼저 하는게 효율적=경사가 완만해짐
->F를 최소화 하려면SPT(증명은 35pg보기)

납기가 있는 문제
L최소화
-L과 F가 dj의 합이 상수라 비례한다
-SPT가 최소화 시켜준다
-납기 신경쓰지 않는 dispatching rule임에도 납기 문제의 최적해를 산출한다
-EDD는 최소화를 보장하지 못한다

Lmax최소화
-EDD가 가능하다(Tmax도 최소화 시켜준다)


U의 수를 최소화
-EDD는 U가 0or1일 때 최선 그러나 2이상 일때는 EDD가 최선을 보장하지 못한다
-U의 수를 최소화 하는 알고리즘
   (1)A와 B 집합을 나눠서 B에 EDD순서로 넣어준다
   (2)순서에 맞게 pj를 합쳐주고 합이 dj를 넘는 순간  멈춘다
   (3)pj중 가장 큰 수를 A집합에 넣어준다
-계속 반복하다가 더 이상 지각이 없는 순간 멈춘다
-B안의 순서(EDD)는 그대로 A는 알아서 나열해도 상관없다(F or Tmax 최소화 하고 싶은데로 계산해서 나열)


the other shops

flow shop scheduling(플로우 샵 스케줄링)
▪ 작업은 초기 시스템에서 여러 중간 시스템을 거쳐 최종 시스템으로 흐릅니다.
완료하기 전에
▪ 작업은 별도의 작업으로 나누어지고 각 작업은 다른 시스템에서 수행됩니다.
▪ 첫 번째 이후의 각 작업에는 정확히 하나의 직접 선행 작업이 있고 마지막 작업 이전의 각 작업에는 정확히 하나의 선행 작업이 있습니다.
직계 후계자 1명
▪ 작업 𝑗의 동작: (1, 𝑗), (2, 𝑗), …, (𝑚, 𝑗)


job shop scheduling(잡샵 스케줄링)
▪ 작업 흐름이 단방향이 아닙니다.
▪ 작업의 첫 번째 작업만 수행하는 초기 머신도 없고, 작업의 마지막 작업만 수행하는 터미널 머신도 없습니다.
▪ 작업 𝑖의 작업 𝑗에는 기계 𝑘이 필요함을 나타내기 위해 세 개의 기호(𝑖,𝑗, 𝑘)를 사용하여 작업을 설명합니다.

-프론트엔드 코드 Vercel에 배포하기

내가 원하는 도메인을 무료 버전으로 하려면 .vercel.app을 넣어줘야 한다

WEST_COLD (westcold.vercel.app)

-도메인 구매하기

아래 영상 참고
카페24 쇼핑몰 도메인 구매부터 적용까지 (도메인 가격비교, 네임서버 변경 방법) (youtube.com)

-Nginx 가 무엇인지 검색하고  ec2 서비스에 설치하기 

nginx는 내 컴퓨터가 서버가 되게 해주는 소프트웨어 
-클라이언트와 WAS사이에서 서빙 및 매니징을 담당하는 역할을 수행
-정적인 요소를 was에 넘어가기 전 미리 서빙해줌 

was란
서버의 동적인 요소를 전문적으로 처리해주는 서버.

Nginx를 사용하는 이유:
1. 리버스 프록시(보안 강화): Nginx는 보안을 강화하는 역할을 한다. 클라이언트와 직접 통신하는 대신 Nginx를 통해 요청을 받아들이면 서버의 IP 주소를 숨길 수 있어 보안을 강화할 수 있다(  한마디로 말하면 클라이언트는 가짜 서버에 요청(request)하면, 프록시 서버가 배후 서버(reverse server)로부터 데이터를 가져오는 역할을 한다 )

2. 로드 밸런싱(부하 분산): Nginx는 요청을 여러 백엔드 서버로 분산하여 부하를 분산할 수 있다. 이를 통해 서버의 안정성과 성능을 향상시킬 수 있다. 

3. 캐싱(정적 파일 서빙): Nginx는 정적 파일(HTML, CSS, JavaScript 등)을 효과적으로 서빙하는 데 사용된다. 이렇게 하면 백엔드 서버가 동적 콘텐츠에만 집중할 수 있고, 정적 파일 서빙은 Nginx가 처리하게 된다.(vercel로 프론트엔드 파일을 처리햇으니 3번은 굳이 지금은 필요없긴 하다) 
 
4.SSL지원: 클라이언트와 HTTPS로 통신하고, 백엔드 서버와 HTTP로 통신하여 보안을 강화하는 역활을 한다. 
 

*설치하기

ec2인스턴스 연결로 들어감 

nginx를 업데이트하고 설치함
sudo apt update
sudo apt install nginx -y 

nginx를 시작하고 부팅 시 자동으로 시작되도록 설정
sudo systemctl start nginx
sudo systemctl enable nginx 

nginx 상태를 확인
sudo systemctl status nginx

  

public ip로 접속해보기 

->aws ip주소 입력을 웹브라우저에 했을때 nginx 웰컴페이지가 떠야한다

-ec2에 파이썬 코드 업로드

git clone https://github.com/your-username/your-repo.git (나중에 업데이트는 git pull origin main) 

(github에 올라온 파이썬 코드 pull로 받아오기)

nano .env 

(.env파일 업로드)

sudo apt update
sudo apt install python3-pip python3-venv -y (파이썬 설치)

python3 -m venv venv(가상 환경 설정)
source venv/bin/activate(가상 환경 활성화)
pip install -r requirements.txt (ex openai같은 모듈 설치)

python your_script.py (코드 실행)



#나중에 가져올때
git init
git commit -m""
git pull origin main

-nginx에서 포트포워딩 설정(aws ip주소를 입력하면 80번 포트가 5000번 포트로 가게끔 처리) 

sudo nano /etc/nginx/sites-available/default

아래 처럼 수정해줌

server {
        listen 80 ;
        listen [::]:80 ;
        server_name _; 

        location / {
        proxy_pass http://127.0.0.1:5000;
        proxy_set_header Host $host;
        proxy_set_header X-Real-IP $remote_addr;
        proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
        proxy_set_header X-Forwarded-Proto $scheme;
        }

Nginx 서비스를 재시작하여 변경 사항을 적용.
sudo systemctl restart nginx

opeanai api에게 내 정보를 물어보면 답이 돌아오는데 시간이 조금 걸려 사용자가 지루할 수 있다.
이를 해결하기 위해 로딩창을 만들어보기로 했다.  


React Spinners (davidhu.io)

 
 우선 아래 코드로 설치해주고 위에 사이트에서 마음에 드는 로딩창을 가져오면 된다
npm i react-spinners --save
add react-spinners
 
-loading.js

 .Loading.css

 
-채팅창 전체 코드

-로딩창

openai api를 활용하면 토큰이 소모가 되는데 이게 사용량이 많으면 돈이 많이 깨진다
잘못하면 누가 마음 먹고 쓸모없는 채팅으로 내 토큰을 소모되게 할 수 있다
이를 해결하기 위해 여러 방법을 사용하여 보안을 구축해보았다.

1.검색어에 나의 대한 질문만 할 수 있게 설정

# 허용되는 키워드 목록
allowed_keywords = ["서찬", "찬", "너", "운영자"]

if any(keyword in user_input for keyword in allowed_keywords):
#생략
else:
    return jsonify({"description": "입력값에 '서찬', '찬', '너', '운영자' 중 하나라도 포함되어야만 실행됩니다."})

2.각 ip마다 질문의 갯수를 제한하여 관리(+하루가 지나면 다시 초기화)

# 제한할 요청 수
REQUEST_LIMIT = 1 # 테스트 목적으로 1로 설정 (원래는 10개)

# IP 주소별 요청 횟수를 저장하는 사전
request_counts = defaultdict(lambda: {'count': 0, 'last_request': None})

def reset_request_count(ip):
    request_counts[ip]['count'] = 0
    request_counts[ip]['last_request'] = datetime.now()

def is_new_day(last_request):
    return datetime.now() - last_request > timedelta(seconds=10) # 테스트 목적으로 10초로 설정 (원래는 days=1)



@app.route('/sendMessage', methods=['POST'])
def send_message():
    data = request.get_json()
    user_input = data.get('user_input')
    #사용자 ip 가져오기
    ip = request.remote_addr

    # 요청 횟수 가져오기
    request_data = request_counts[ip]
    count = request_data['count']
    last_request = request_data['last_request']

    # 하루가 지났는지 확인하여 요청 횟수 초기화
    if last_request is None or is_new_day(last_request):
        reset_request_count(ip)

    if count >= REQUEST_LIMIT:
        return jsonify({"description": "질문이 초과했습니다ㅠㅠ"})
    else:
        request_counts[ip]['count'] += 1
        request_counts[ip]['last_request'] = datetime.now()

-중간에 질문이 데이터 베이스에 저장하는데 쓰레드에 여러 질문이 들어와 저장이 안되고 또한 질문의 답 출력하는데 오류가 나길래 쓰레드를 각ip마다 주었다

# IP 주소별 스레드 ID를 저장하는 사전
thread_ids = {}

# 새로운 스레드 생성 함수
def create_new_thread():
    response = client.beta.threads.create()
    # response의 구조를 출력해보자
    print(response)
    # response 객체의 속성에 맞게 접근
    return response.id
    
# sendMessage 라우터
@app.route('/sendMessage', methods=['POST'])
def send_message():
    data = request.get_json()
    user_input = data.get('user_input')
    ip = request.remote_addr

    # 요청 횟수 가져오기
    request_data = request_counts[ip]
    
# IP 주소별 스레드 ID 가져오기
        if ip not in thread_ids:
            thread_id = create_new_thread()
            thread_ids[ip] = thread_id
        else:
            thread_id = thread_ids[ip]

        # AI 응답 가져오기
        ai_response = get_ai_response(user_input, thread_id)

3. 잘못된 질문을 계속하면 차단하기

인스트럭션에 "서찬에 대한 질문이 아니면 "false" 라고만 대답해줘"라는 명령을 주어 false가 3번 이상 나오면 더 이상 opanai api가 실행되지 않게 설정해준다

request_counts = defaultdict(lambda: {'count': 0, 'last_request': None, 'false_count': 0})

def reset_request_count(ip):
    request_counts[ip]['count'] = 0
    request_counts[ip]['last_request'] = datetime.now()
    request_counts[ip]['false_count'] = 0
   
@app.route('/sendMessage', methods=['POST'])
def send_message():
    data = request.get_json()
    user_input = data.get('user_input')
    ip = request.remote_addr

    # 요청 횟수 가져오기
    request_data = request_counts[ip]
    count = request_data['count']
    last_request = request_data['last_request']
    false_count = request_data['false_count']
    
    # false_count가 3 이상이면 차단
    if false_count >= 3:
        return jsonify({"description": "너무 많은 잘못된 응답으로 인해 차단되었습니다."})
        
    else:
         # AI 응답 가져오기
        ai_response = get_ai_response(user_input, thread_id)

        # 'False' 응답 횟수 증가
        if ai_response.strip().lower() == 'false':
            request_counts[ip]['false_count'] += 1

4.데이터베이스에 사용자가 어떤 질문을 하는지와 어떤 사용자가 어떤 질문을 하는지 확인하게 사용자 ip를 저장하기

from openai import OpenAI
import time
from flask import Flask, request, jsonify
from flask_cors import CORS
import pymysql
from collections import defaultdict
from datetime import datetime, timedelta

# MySQL 데이터베이스 연결 설정 함수
def get_database_connection():
    return pymysql.connect(host="localhost", user="root", password="", db="", charset="")
    
    # 데이터베이스에 저장
            try:
                db_connection = get_database_connection()
                cursor = db_connection.cursor()
                query = "INSERT INTO portpolio.portpolio_input (ip, comments, answer) VALUES (%s, %s, %s)"
                cursor.execute(query, (str(ip), user_input, ai_response))
                db_connection.commit()
                return jsonify({"description": ai_response})

            except Exception as e:
                return jsonify({"description": "데이터 저장 중 오류가 발생하였습니다: " + str(e)})

            finally:
                cursor.close()
                db_connection.close()

-전체 코드

(검색어를 미리 설정 하는 건 비효율적이라는 피드백을 받아 수정->새로운 로직)

from openai import OpenAI
import time
from flask import Flask, request, jsonify
from flask_cors import CORS
import pymysql
from collections import defaultdict
from datetime import datetime, timedelta

app = Flask(__name__)
CORS(app)  # 모든 출처에서의 요청을 허용합니다.

# OpenAI API 키 설정
client = OpenAI(api_key="")

# 제한할 요청 수
REQUEST_LIMIT = 5  # 테스트 목적으로 1로 설정 (원래는 10개)

# IP 주소별 요청 횟수를 저장하는 사전
request_counts = defaultdict(lambda: {'count': 0, 'last_request': None, 'false_count': 0})

# IP 주소별 스레드 ID를 저장하는 사전
thread_ids = {}

def reset_request_count(ip):
    request_counts[ip]['count'] = 0
    request_counts[ip]['last_request'] = datetime.now()
    request_counts[ip]['false_count'] = 0

def is_new_day(last_request):
    return datetime.now() - last_request > timedelta(seconds=50)  # 테스트 목적으로 5초로 설정 (원래는 days=1)

# MySQL 데이터베이스 연결 설정 함수
def get_database_connection():
    return pymysql.connect(host="", user="t", password="", db="", charset="")

# 새로운 스레드 생성 함수
def create_new_thread():
    response = client.beta.threads.create()
    # response의 구조를 출력해보자
    print(response)
    # response 객체의 속성에 맞게 접근
    return response.id

# AI 응답을 가져오는 함수
def get_ai_response(user_input, thread_id):
    try:
        assistant_id = ""

        message = client.beta.threads.messages.create(
            thread_id,
            role="user",
            content=user_input,
        )

        run = client.beta.threads.runs.create(
            thread_id=thread_id,
            assistant_id=assistant_id,
        )

        run_id = run.id

        while True:
            run = client.beta.threads.runs.retrieve(
                thread_id=thread_id,
                run_id=run_id,
            )
            if run.status == "completed":
                break
            else:
                time.sleep(2)

        thread_messages = client.beta.threads.messages.list(thread_id)
        ai_response = thread_messages.data[0].content[0].text.value

        return ai_response

    except Exception as e:
        return str(e)

# sendMessage 라우터
@app.route('/sendMessage', methods=['POST'])
def send_message():
    data = request.get_json()
    user_input = data.get('user_input')
    ip = request.remote_addr

    # 요청 횟수 가져오기
    request_data = request_counts[ip]
    count = request_data['count']
    last_request = request_data['last_request']
    false_count = request_data['false_count']

    # 하루가 지났는지 확인하여 요청 횟수 초기화
    if last_request is None or is_new_day(last_request):
        reset_request_count(ip)

    # false_count가 3 이상이면 차단
    if false_count >= 3:
        return jsonify({"description": "너무 많은 잘못된 응답으로 인해 차단되었습니다."})


    # 요청 횟수 확인
    if count >= REQUEST_LIMIT:
        return jsonify({"description": "질문이 초과했습니다ㅠㅠ"})


    # 요청 횟수 증가
    request_counts[ip]['count'] += 1
    request_counts[ip]['last_request'] = datetime.now()

    # IP 주소별 스레드 ID 가져오기
    if ip not in thread_ids:
        thread_id = create_new_thread()
        thread_ids[ip] = thread_id
    else:
        thread_id = thread_ids[ip]

    # AI 응답 가져오기
    ai_response = get_ai_response(user_input, thread_id)

    # 'False' 응답 횟수 증가
    if ai_response.strip().lower() == 'false':
        request_counts[ip]['false_count'] += 1

    # 데이터베이스에 저장
    try:
        db_connection = get_database_connection()
        cursor = db_connection.cursor()
        query = "INSERT INTO portpolio.portpolio_input (ip, comments, answer) VALUES (%s, %s, %s)"
        cursor.execute(query, (str(ip), user_input, ai_response))
        db_connection.commit()
        return jsonify({"description": ai_response})

    except Exception as e:
        return jsonify({"description": "데이터 저장 중 오류가 발생하였습니다: " + str(e)})

    finally:
        cursor.close()
        db_connection.close()

if __name__ == '__main__':
    print("Flask 애플리케이션이 실행되었습니다.")
    app.run(debug=True)

로직의 순서

하루마다 검색어 초기화->false 3번 했는지->ip마다 요청횟수->ip마다 쓰레드 만들기->ai에게 질문

이번 과제를 하며 느낀점
-사실 코딩 할 때 chatgpt한테 물어보는 경우가 많은데 아무리 편하다해도 조금 복잡한 로직은 오류가 많이 나서 시간이 오래 걸렸다. 그러나 한번 천천히 코드 읽어가면서 로직?을 이해하며 수정하니 30분이면 끝나는 경우도 많았다. 이를 통해 chatgpt에게 물어보기 전 먼저 내가 그 로직을 구상 + 코드가 나오면 로직을 읽는 버릇이 필요하다 느낌

과제
Open AI 어시스턴스 만들기
어시스턴트와 관련 된 기본용어 찾아서 정리해보기, 어시스턴트id,스레드id
어시스턴트에 간단하게 이력서샘플 만들어서 업로드
어시스턴트 api로 바꾸기

Assistants API 구조

기본요소

*assistant=목적에 맞는 로봇
 

from openai import OpenAI
import time


# OpenAI API 키 설정
client = OpenAI(api_key="")

#assistant 생성
assistant = client.beta.assistants.create(
     name="Math Tutor",
     instructions="You are a personal math tutor. Answer questions briefly, in a sentence or less.",
     model="gpt-3.5-turbo",
 )
# # 생성된 챗봇의 정보를 JSON 형태로 출력합니다.
print(assistant)

assistant_id=""

*thread=카톡 방,하나의 thread 안에 여러개의 메세지 존재

# # # 새로운 스레드를 생성합니다.
thread = client.beta.threads.create()

print(thread)

#resume thread
thread_id = ""

*message=thread 안에 있는 대화들
 
종류
-system:어시스턴트가 참고할 만한 전역조건
-user: 사용자의 질문
-assistant: ai의 답변
 
thread는 여러개의 메세지를 가지고 있을 수 있다
 
message{
role:user//user 메세지
content는 물어보고 싶은 거 담으면 된다
}

message = client.beta.threads.messages.create(
    thread_id,
    role="user",
    content="서찬의 전화번호 알고 싶습니다",
)

print(message)

 

*run:어시스턴트가 정해진 대화를 통해 객채를 만듬, 실행시점을 관리

어시스턴트와 쓰레드는 독립(수학 과학 관련된 로봇과 관련없는 수학과 과학 관련된 카톡방)
일관성을 위해 하나의 주제에 맞는 어시스턴트에 하나의 주제에 맞는 쓰레드가 좋다

run을 사용할 때는 쓰레드와 어시스턴트가 독립적이기에 각각 아이디를 받아온다

status
queued 대기중-비동기처리로 단계관리하기 위해->원하는 시점에 데이터를 받아 올 수 있다
completed 질문 답변 완료

list로 답변 확인
 

# 실행할 Run 을 생성합니다.
# Thread ID 와 Assistant ID 를 지정합니다.
run = client.beta.threads.runs.create(
  thread_id="",
  assistant_id="",
)

print(run)

run_id = run.id

while True:
  run = client.beta.threads.runs.retrieve(
    thread_id=thread_id,
    run_id= run_id,
  )
  if run.status == "completed":
    break
  else:
    time.sleep(2)
  # print(run)


thread_messages = client.beta.threads.messages.list(thread_id)
print(thread_messages.data[0].content[0].text.value)

Assistants API

->chatgpt의 텍스트 형식의 도구의 제약을 해소하기 위해 탄생

code interpreter
-디버깅과 다른 느낌
-토큰 제한수를 넘는 데이터를 위해 쿼리문을 작성해서 토큰을 효율적이게 사용
-쉽게 말해 엄청난 양의 데이터 분석 가능

retrieval
-검색
-우리의 자료로 결과를 낼 수 있다
-문서를 gpt에게 학습을 시켜 그 문서를 토대로 답변을 해준다


function
-내가 만든 함수를 기반으로 어시스턴트가 사용할 수 있게 만들어준다(예를들어 검색으로 학습한 문서를 기반으로 함수를 만들 수 있다)

Retreieval을 활용하여 이력서 학습을 시켜 나만의 챗봇 만들기

1. openai api 사이트에서 내가 만든 어시스턴트에 내 이력서 파일을 넣어준다(+추가로 instructions도 수정 가능)
 

 
2. 프로트엔드 서버에서 입력값 받아와 출력하기
 
아래 블로그에서 참고
Front & Back 서버 연결(axios 실습) :: West_Cold (tistory.com)

from openai import OpenAI
import time
from flask import Flask, request, jsonify
from flask_cors import CORS

app = Flask(__name__)
CORS(app)  # 모든 출처에서의 요청을 허용합니다.

# OpenAI API 키 설정
client = OpenAI(api_key="")


@app.route('/sendMessage', methods=['POST'])
def send_message():
    data = request.get_json()
    user_input = data.get('user_input')

    try:
        assistant_id=""

        #resume thread
        thread_id = ""

        message = client.beta.threads.messages.create(
            thread_id,
            role="user",
            content=user_input,
        )

        # 실행할 Run 을 생성합니다.
        # Thread ID 와 Assistant ID 를 지정합니다.
        run = client.beta.threads.runs.create(
          thread_id=thread_id,
          assistant_id=assistant_id,
        )

        run_id = run.id

        while True:
          run = client.beta.threads.runs.retrieve(
            thread_id=thread_id,
            run_id= run_id,
          )
          if run.status == "completed":
            break
          else:
            time.sleep(2)


        thread_messages = client.beta.threads.messages.list(thread_id)
        ai_response = thread_messages.data[0].content[0].text.value

        return jsonify({"description": ai_response})

    except Exception as e:
        return jsonify({"error": str(e)})

if __name__ == '__main__':
    print("Flask 애플리케이션이 실행되었습니다.")
    app.run(debug=True)

 
3. 결과

참고영상

https://youtu.be/kKhWkG5Di5s?si=Pvi8JbR_vmqZcdpt

https://youtu.be/-Wne4a-8RlY?si=bpn6IyXQIQBXal86