ToC
모빌리티서비스
- 9주에 했던 내용 다시 실행
- 실습 예고: 가상 머신을 하나 더 만들거나, 아예 리눅스 PC를 새로 장만하면 좋다.
- 피자 먹었음. 맛있었음.
알고리즘
- 유전 알고리즘 복습
- 랜덤한 해를 생성하고(
P_0) 각 해의 cost 계산 - 랜덤한 두 부모를 선택 후 교배(원하는 방식대로 섞기)
- 낮은 확률로 돌연변이 발생(랜덤하게 뭔가 바뀜)
- 생성된 자식은 전체 유전자 풀에서 안 좋은 해를 대체함
- 위의 과정을 반복
- 특정한 조건 하에 반복을 중단하고 가장 좋은 해를 반환함
- 랜덤한 해를 생성하고(
- 유전 알고리즘 세부 구현의 다양한 변형
- 부모 선택 알고리즘: 룰렛 휠, 토너먼트, 사회복지(전체에서 특별히 cost가 높은 유전자의 cost 보정해주기)
- 교배 방식(일관된 규칙이 있기만 하면 됨): 일정한 모양/비율로 분할, 각 자리마다 랜덤한 확률로 부모 중 하나 선택, 랜덤한 확률로 부모 복제, (2차원 이상)해를 잘라서 이어붙임, 1% - 0.01% 확률로 돌연변이 발생(확률 고정, 감소 방식), 얌체 교배, 양봉
- 세대 교체 방식: steady-state(매번 대체), generational(세대별 대체), Preselection(부모 대체), Crowding(유사값 대체), Eliticism(엘리트주의, 특별히 cost가 낮은 해가 대체되지 않게 보호), 재산비례(cost가 낮을수록 자식을 많이 만듦), Island Method(Parallel, 콜럼버스 방식, 대륙을 나누어 각자 수렴진화 후 대륙 간 교배), 천적관계(두 그룹이 서로를 공격하며 진화)
- 구현 시 예상되는 어려움
초기에는 해가 성립하거나 성립하지 않는 특정 조건(예: 1이 무조건 6개 이상, F 다음에는 A가 오면 안 됨)을 고려하여 부모를 생성하기 때문에, 초기 전체 풀은 ‘해로 사용 가능함(feasible)’이 보장된다. 하지만 교배 방식에 따라 자식은 해의 조건을 충족하지 않을 수 있다. 고로 자식을 생성할 때 자식해를 적절하게 수정할 필요가 있을 수 있다. - 활용 사례
- 다항식 최적화
다항식의 계수 벡터를 유전 알고리즘의 해로 간주하고, 정해진 변수 값에 따라 그에 맞는 답을 만들어낼 수 있는 최적의 계수 조합을 찾음. - 신경망 가중치 최적화
초기 가중치 셋을 구할 때 유전 알고리즘을 사용한 후 오차 역전파를 수행하면 더 빠르다고 한다. - 엘리베이터 스케줄링
- 차량 라우팅: 타다, 우버 등의 카 헤일링/쉐어링 서비스에서 요청이 있는 고객에게 효율적으로 차량 배치하기
- 단백질 3차원 구조
- VLSI 회로 배치
- Vector quantization
- 죄수 딜레마
- 다항식 최적화
소프트웨어분석및설계
- 시퀀스 다이어그램 복습, 진도 나감
- 시나리오 중 객체 생성, 삭제
- 시퀀스 다이어그램에 프레임 씌우기: 참조, 대안(if-else), 동시 진행 표기 가능
- 통신 다이어그램: 수업 내용 기억 안 남
- 객체지향
- 선언과 구현 분리: 컴파일러는 선언부와 구현부가 따로 있으면 따로 컴파일한다. 일반적으로 권장됨.
- java: java는 C++에 대한 반항으로 태어난 언어이다. C/C++은 포인터 사용으로 인한 오류가 너무 많았고, 보안에 취약했다. 대신 속도는 압도적으로 빠르다.
- C++과 java의 차이 위주로 확인
- 언어에 따라 다르지만 java는 다중상속이 불가하고 C++은 가능하다.
- (약한) 집합 연관: 자바는 포인터가 없어서 그대로 쓸 수는 없음. C++은 포인터를 사용하기 때문에 상위 객체가 삭제되어도 하위 객체가 남는다.
- 복합 연관의 표현: 맨 앞에 언더바가 붙는 이름은 private이니 건드리지 말라는 암묵적 표시
- 이진 연관: 양방향 연관. 관계가 끊어지거나 변경될 때 양쪽 객체 모두가 업데이트되어야 함.
소프트웨어디자인패턴
- State 패턴
- 유한 상태 머신 패턴. 각 상태는 서로 다른 클래스로 표현된다.
- 객체의 모든 가능한 상태에 대한 클래스를 만들고 각 상태별 작업을 위임하여 처리함
- 구체상황과 상태, 구체상태. 구체상황은 현재의 상태를 나타내는 구체상태를 하나 갖고 있으며, 자체적으로 행동하지 않고 해당 구체상태 클래스에 위임한다.
- 겉보기에 모든 동작을 구체상황 클래스가 수행하는 것처럼 보이지만 내부적으로는 각 구체상태 클래스가 수행하고 있고, main 입장에서는 현재 상태를 알 수 없다.
- 개개의 구체적인 상태를 각각 클래스로 나누어서 표현함으로써 문제를 분할, 상태의 종류가 많을수록 유용하다.
- 상태에 따라 행동이 달라지는 처리
- 새로운 상태를 추가하는 것은 간단하나, 상태의 수가 적거나 머신이 거의 변경되지 않을 때 이 패턴을 사용하는 것은 추천되지 않는다.
- 시퀀스 다이어그램 팁: 보낸 메시지가 돌아올 때 그 전후상황을 알아야 한다면 라이프라인이 연결되어 있어야 하고, 그럴 필요가 없다면 라이프라인 잘라도 됨. 케이크 잘 그리기.